Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

On Rigid Matrices and U-Polynomials

RSS-Feed




Revision #1
Authors: Noga Alon, Gil Cohen
Accepted on: 29th October 2012 22:14
Downloads: 2033
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
Downloads: 2063
Keywords: 


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.



ISSN 1433-8092 | Imprint