[My Computational Complexity Web Log] Final Notes from Banff
Some final notes from the Banff workshop. First a few lemmas used in Wigderson's talk.
Lemma 1: Let G=(V,E) with n vertices and m edges and m≥4n. Let cr(G) be the number of edge crossings in any planer layout of G. Then cr(G)≥m3/64n2.
Lemma 2 (Trotter-Szemérdi): Suppose we have a set of points P and lines L in the plane. Let n=|P| and m=|L|. Let I be the number of indices, i.e. the number of pairs (p,l) with p in P, l in L and line l contains the point p. Then |I| ≤ 4((mn)2/3+m+n).
Guy Kindler talked about a brand new set of results with Barak, Shaltiel, Sudakov and Wigderson. Among other things they improve on the Barak-Impagliazzo-Wigderson result I mentioned earlier by showing that for any constant δ>0, one can take seven independent sources of n bits each with δn min-entropy and combine them to get O(δn) bits of randomness.
Mario Szegedy talked about his recent work showing that the quantum hitting time of a symmetric ergodic Markov chains is the square root of the classical hitting time, a result that becomes a powerful tool in developing quantum algorithms.
Posted by Lance to My Computational Complexity Web Log at 7/11/2004 08:50:59 AM