Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR12-144 | 6th November 2012 14:41

On a special case of rigidity

RSS-Feed




TR12-144
Authors: Rocco Servedio, Emanuele Viola
Publication: 6th November 2012 14:42
Downloads: 3388
Keywords: 


Abstract:

We highlight the special case of Valiant's rigidity
problem in which the low-rank matrices are truth-tables
of sparse polynomials. We show that progress on this
special case entails that Inner Product is not computable
by small \acz circuits with one layer of parity gates
close to the inputs. We then prove that the sign of any
-1/1 polynomial with \le s monomials in 2n
variables disagrees with Inner Product in \ge \Omega(1/s) fraction of inputs, a type of result that
seems unknown in the rigidity setting.



ISSN 1433-8092 | Imprint