{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T01:15:58Z","timestamp":1648689358153},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2015,9,17]],"date-time":"2015-09-17T00:00:00Z","timestamp":1442448000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2015,12]]},"DOI":"10.1007\/s00037-015-0112-9","type":"journal-article","created":{"date-parts":[[2015,9,17]],"date-time":"2015-09-17T03:55:19Z","timestamp":1442462119000},"page":"851-879","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On Rigid Matrices and U-Polynomials"],"prefix":"10.1007","volume":"24","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[]},{"given":"Gil","family":"Cohen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,9,17]]},"reference":[{"key":"112_CR1","doi-asserted-by":"crossref","unstructured":"N. Alon, J. Bruck, J. Naor, M. Naor & R. Roth (1992a). Construction of Asymptotically Good Low-Rate Error-Correcting Codes through Pseudo-Random Graphs. IEEE Transactions on Information Theory 38, 509\u2013516.","DOI":"10.1109\/18.119713"},{"issue":"1","key":"112_CR2","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/0012-365X(88)90189-6","volume":"72","author":"N. Alon","year":"1988","unstructured":"Alon N., Chung F.R.K. (1988) Explicit Construction of Linear Sized Tolerant Networks. Discrete Mathematics 72(1): 15\u201319","journal-title":"Discrete Mathematics"},{"issue":"3","key":"112_CR3","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1002\/rsa.3240030308","volume":"3","author":"N. Alon","year":"1992","unstructured":"Alon N., Goldreich O., H\u00e5stad J., Peralta R. (1992) Simple Construction of Almost k-wise Independent Random Variables. Random Structures and Algorithms 3(3): 289\u2013304","journal-title":"Random Structures and Algorithms"},{"key":"112_CR4","doi-asserted-by":"crossref","unstructured":"N. Alon, R. Panigrahy & S. Yekhanin (2009). Deterministic approximation algorithms for the nearest codeword problem. In APPROX 09 \/ RANDOM 09: Proceedings of the 12th International Workshop and 13th International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 339\u2013351.","DOI":"10.1007\/978-3-642-03685-9_26"},{"issue":"2","key":"112_CR5","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1002\/rsa.3240050203","volume":"5","author":"N. Alon","year":"1994","unstructured":"Alon N., Roichman Y. (1994) Random Cayley Graphs and Expanders. Random Structures and Algorithms 5(2): 271\u2013285","journal-title":"Random Structures and Algorithms"},{"key":"112_CR6","unstructured":"V. Arvind & S. Srinivasan (2010). The Remote Point Problem, Small Bias Spaces, and Expanding Generator Sets. In Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS), 59\u201370."},{"key":"112_CR7","doi-asserted-by":"crossref","unstructured":"A. Ben-Aroya & A. Ta-Shma (2009). Constructing small-bias sets from algebraic-geometric codes. In Proceedings of the 50th Annual IEEE symposium on Foundations of Computer science (FOCS), 191\u2013197.","DOI":"10.1109\/FOCS.2009.44"},{"key":"112_CR8","doi-asserted-by":"crossref","unstructured":"Z. Dvir (2010). On Matrix Rigidity and Locally Self-Correctable Codes. In Proceedings of the 25th IEEE Conference on Computational Complexity (CCC), 291\u2013298.","DOI":"10.1109\/CCC.2010.35"},{"issue":"2","key":"112_CR9","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/BF01303207","volume":"13","author":"J. Friedman","year":"1993","unstructured":"Friedman J. (1993) A note on matrix rigidity. Combinatorica 13(2): 235\u2013239","journal-title":"Combinatorica"},{"issue":"4","key":"112_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1538902.1538904","volume":"56","author":"V. Guruswami","year":"2009","unstructured":"Guruswami V., Umans C., Vadhan S. (2009) Unbalanced expanders and randomness extractors from Parvaresh\u2013Vardy codes. J. ACM 56(4): 1\u201334","journal-title":"J. ACM"},{"key":"112_CR11","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","volume":"43","author":"S. Hoory","year":"2006","unstructured":"Hoory S., Linial N., Wigderson A. (2006) Expander Graphs and their Applications. Bulleting of the American Mathematical Society 43: 439\u2013561","journal-title":"Bulleting of the American Mathematical Society"},{"issue":"4","key":"112_CR12","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1007\/BF02311250","volume":"63","author":"B.S. Kashin","year":"1998","unstructured":"Kashin B.S., Razborov A.A. (1998) Improved lower bounds on the rigidity of Hadamard matrices. Mathematical Notes 63(4): 471\u2013475","journal-title":"Mathematical Notes"},{"key":"112_CR13","doi-asserted-by":"crossref","unstructured":"S. V. Lokam (1995). Spectral Methods for Matrix Rigidity with Applications to Size-Depth Tradeoffs and Communication Complexity. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS), 6\u201315.","DOI":"10.1109\/SFCS.1995.492457"},{"issue":"1-2","key":"112_CR14","first-page":"1","volume":"4","author":"S.V. Lokam","year":"2009","unstructured":"Lokam S.V. (2009) Complexity Lower Bounds using Linear Algebra. Foundations and Trends in Theoretical Computer Science 4(1-2): 1\u2013155","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"112_CR15","unstructured":"F. J. MacWilliams & N. J. A. Sloane (1977). The Theory of Error-Correcting Codes, Part II. North-Holland."},{"issue":"4","key":"112_CR16","doi-asserted-by":"crossref","first-page":"838","DOI":"10.1137\/0222053","volume":"22","author":"J. Naor","year":"1993","unstructured":"Naor J., Naor M. (1993) Small-Bias Probability Spaces: Efficient Constructions and Applications. SIAM J. on Computing 22(4): 838\u2013856","journal-title":"SIAM J. on Computing"},{"key":"112_CR17","doi-asserted-by":"crossref","unstructured":"R. O\u2019Donnell (2014). Analysis of boolean functions. Cambridge University Press.","DOI":"10.1017\/CBO9781139814782"},{"key":"112_CR18","first-page":"327","volume":"13","author":"P. Pudl\u00e1k","year":"2004","unstructured":"Pudl\u00e1k P., R\u00f6dl V. (2004) Pseudorandom sets and explicit constructions of Ramsey graphs. Quad. Mat 13: 327\u2013346","journal-title":"Quad. Mat"},{"issue":"6","key":"112_CR19","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1016\/S0020-0190(97)00190-7","volume":"64","author":"M.A. Shokrollahi","year":"1997","unstructured":"Shokrollahi M.A., Spielman D., Stemann V. (1997) A remark on matrix rigidity. Information Processing Letters 64(6): 283\u2013285","journal-title":"Information Processing Letters"},{"key":"112_CR20","doi-asserted-by":"crossref","unstructured":"L. G. Valiant (1977). Graph-theoretic arguments in low-level complexity. In Lecture notes in Computer Science, volume 53, 162\u2013176. Springer.","DOI":"10.1007\/3-540-08353-7_135"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-015-0112-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-015-0112-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-015-0112-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T11:01:59Z","timestamp":1558522919000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-015-0112-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9,17]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,12]]}},"alternative-id":["112"],"URL":"https:\/\/doi.org\/10.1007\/s00037-015-0112-9","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,9,17]]}}}