@inproceedings{4a725124f74e41f6b1428e19ffc812b9,
title = "On rigid matrices and U-polynomials",
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.",
keywords = "U-polynomials, matrix rigidity, small-bias sets, unbalanced expanders",
author = "Noga Alon and Gil Cohen",
year = "2013",
doi = "10.1109/CCC.2013.28",
language = "English (US)",
isbn = "9780769549972",
series = "Proceedings of the Annual IEEE Conference on Computational Complexity",
pages = "197--206",
booktitle = "Proceedings - 2013 IEEE Conference on Computational Complexity, CCC 2013",
note = "2013 IEEE Conference on Computational Complexity, CCC 2013 ; Conference date: 05-06-2013 Through 07-06-2013",
}