ECCC-Report TR12-144https://eccc.weizmann.ac.il/report/2012/144Comments and Revisions published for TR12-144en-usTue, 06 Nov 2012 14:42:11 +0200
Paper TR12-144
| On a special case of rigidity |
Rocco Servedio,
Emanuele Viola
https://eccc.weizmann.ac.il/report/2012/144We 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.Tue, 06 Nov 2012 14:42:11 +0200https://eccc.weizmann.ac.il/report/2012/144