On Rigid Matrices and U-Polynomials

Noga Alon, Gil Cohen

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


We introduce a class of polynomials, which we call U-polynomials, and show that the problem of explicitly constructing a rigid matrix can be reduced to the problem of explicitly constructing a small hitting set for this class. We prove that small-bias sets are hitting sets for the class of U-polynomials, though their size is larger than desired. Furthermore, we give two alternative proofs for the fact that small-bias sets induce rigid matrices. Finally, we construct rigid matrices from unbalanced expanders, with essentially the same size as the construction via small-bias sets.

Original languageEnglish (US)
Pages (from-to)851-879
Number of pages29
JournalComputational Complexity
Issue number4
StatePublished - Dec 1 2015

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Mathematics
  • Computational Theory and Mathematics
  • Computational Mathematics


  • Matrix rigidity
  • small-bias sets
  • unbalanced expanders


Dive into the research topics of 'On Rigid Matrices and U-Polynomials'. Together they form a unique fingerprint.

Cite this