Computational Complexity

Sunday, July 11, 2004

 
Final Notes from Banff

Posted by Lance

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)≥m³/64n².

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.

Update 7/12: Group Photo now online.

8:50 AM # 1 comments

1.  Jeff Erickson says:  
   
   Credit for Lemma 2 should be shared with L�szl� Sz�kely, who published a beautiful, self-contained, probabilistic "Book proof" of the Szem�redi-Trotter incidence bound (Lemma 2), as well as the crossing lemma (Lemma 1) it depends on. The constant 4 in the incidence upper bound comes from Sz�kely's proof; the corresponding constant in Szem�redi and Trotter's original paper was astronomical.
   

   3:22 PM, July 12, 2004

Comment Feeds: This Post All