__
TR10-086 | 17th May 2010 10:20
__

#### On a Theorem of Razborov

**Abstract:**
In an unpublished Russian manuscript Razborov proved that a matrix family with high

rigidity over a finite field would yield a language outside the polynomial hierarchy

in communication complexity.

We present an alternative proof that strengthens the original result in several ways.

In particular, we replace rigidity by the strictly weaker notion of toggle rigidity.

It turns out that Razborov's astounding result is actually a corollary of a slight

generalization of Toda's First Theorem in communication complexity, and that matrix

rigidity over a finite field is a lower-bound method for bounded-error modular

communication complexity.

We also give evidence that Razborov's strategy is a promising one by presenting a

protocol with few alternations for the inner product function mod two and by discussing

problems possibly outside the communication complexity version of the polynomial

hierarchy.