ECCC-Report TR12-133https://eccc.weizmann.ac.il/report/2012/133Comments and Revisions published for TR12-133en-usMon, 29 Oct 2012 22:14:13 +0200
Revision 1
| On Rigid Matrices and U-Polynomials |
Noga Alon,
Gil Cohen
https://eccc.weizmann.ac.il/report/2012/133#revision1We 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.
Mon, 29 Oct 2012 22:14:13 +0200https://eccc.weizmann.ac.il/report/2012/133#revision1
Paper TR12-133
| On Rigid Matrices and Subspace Polynomials |
Noga Alon,
Gil Cohen
https://eccc.weizmann.ac.il/report/2012/133We 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.
Sun, 21 Oct 2012 13:31:02 +0200https://eccc.weizmann.ac.il/report/2012/133