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.
Update 7/12: Group Photo now online.
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.
ReplyDelete