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: 1555
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