@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",

note = "Copyright: Copyright 2013 Elsevier B.V., All rights reserved.; 2013 IEEE Conference on Computational Complexity, CCC 2013 ; Conference date: 05-06-2013 Through 07-06-2013",

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",

}