ECCC-Report TR10-086https://eccc.weizmann.ac.il/report/2010/086Comments and Revisions published for TR10-086en-usThu, 20 May 2010 15:10:18 +0300
Paper TR10-086
| On a Theorem of Razborov |
Henning Wunderlich
https://eccc.weizmann.ac.il/report/2010/086In 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.
Thu, 20 May 2010 15:10:18 +0300https://eccc.weizmann.ac.il/report/2010/086