On a special case of rigidity
R. Servedio and E. Viola.
ECCC Technical Report 144, 2012.


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 AC^0 circuits with one layer of parity gates close to the inputs. We then prove that the sign of any $-1/1$ polynomial with $s$ monomials in $2n$ variables disagrees with Inner Product in $\Omega(1/s)$ fraction of inputs, a type of result that seems unknown in the rigidity setting.

Link to open-access ECCC report.


Back to main papers page