Abstract: I will give a short introduction to quantum communication complexity and will discuss related geometrical lemmas and open problems . No previous knowledge in complexity theory or quantum mechanics is assumed.

Communication complexity has become a central complexity model. In that model, we count the amount of communication bits needed between two parties in order to solve certain computational problems. The main result discussed in the talk shows that for certain communication complexity problems quantum communication protocols are much faster (exponentially faster) than classical ones.

The result is of a geometrical nature. In order to prove our result, we prove several lemmas about the geometry of the (real) sphere S^n, and about sets of orthogonal matrices. One (relatively simple) example is the following lemma:

Let C be a measurable set of measure (fraction) c, in the sphere S^n. Let V be a random linear subspace of dimension k in R^(n+1), and denote by g_V the measure (fraction) of (C \cap V) in the sphere (S^n \cap V). Then, for any \delta>0,
PROB_V [ | g_V - c | >= \delta ] < (4/\delta) e^{-k\delta^2/2}.
That is, with very high probability g_V is very close to c (as expected).