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.
main papers page
Back to main papers page