**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^{3}/64n^{2}.

**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.

## No comments:

## Post a Comment