On rigid matrices and U-polynomials

Noga Alon, Gil Cohen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

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)
Title of host publicationProceedings - 2013 IEEE Conference on Computational Complexity, CCC 2013
Pages197-206
Number of pages10
DOIs
StatePublished - 2013
Event2013 IEEE Conference on Computational Complexity, CCC 2013 - Palo Alto, CA, United States
Duration: Jun 5 2013Jun 7 2013

Publication series

NameProceedings of the Annual IEEE Conference on Computational Complexity
ISSN (Print)1093-0159

Other

Other2013 IEEE Conference on Computational Complexity, CCC 2013
CountryUnited States
CityPalo Alto, CA
Period6/5/136/7/13

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Computational Mathematics

Keywords

  • U-polynomials
  • matrix rigidity
  • small-bias sets
  • unbalanced expanders

Fingerprint Dive into the research topics of 'On rigid matrices and U-polynomials'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., & Cohen, G. (2013). On rigid matrices and U-polynomials. In Proceedings - 2013 IEEE Conference on Computational Complexity, CCC 2013 (pp. 197-206). [6597762] (Proceedings of the Annual IEEE Conference on Computational Complexity). https://doi.org/10.1109/CCC.2013.28