Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR12-133 | 29th October 2012 22:14

#### On Rigid Matrices and U-Polynomials

Revision #1
Authors: Noga Alon, Gil Cohen
Accepted on: 29th October 2012 22:14
Keywords:

Abstract:

We introduce a class of polynomials, which we call \emph{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.

Changes to previous version:

Replaced the term Subspace Polynomials, which appears in the literature with a different meaning, with U-polynomials.

### Paper:

TR12-133 | 21st October 2012 09:56

#### On Rigid Matrices and Subspace Polynomials

TR12-133
Authors: Noga Alon, Gil Cohen
Publication: 21st October 2012 13:31