יום חמישי, ב' באדר ב', תשס"ג

Thursday, 6th March 2003, 4:00 pm

Mathematics Building, Lecture Hall 2

Ran Raz

(Weizmann)

"Quantum Communication and Geometrical Properties of the Sphere
*S^n*"

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

Light refreshments will be served in the faculty lounge at 3:30.

List of talks, 2002-03

List of talks, 2001-02

List of talks, 2000-01

List of talks, 1998-99

List of talks, 1997-98