Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-086 | 17th May 2010 10:20

On a Theorem of Razborov



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

ISSN 1433-8092 | Imprint