__
Revision #1 to TR12-133 | 29th October 2012 22:14
__
#### On Rigid Matrices and U-Polynomials

**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.

__
TR12-133 | 21st October 2012 09:56
__

#### On Rigid Matrices and Subspace Polynomials

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