{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T13:52:17Z","timestamp":1760709137860},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,9,1]],"date-time":"2016-09-01T00:00:00Z","timestamp":1472688000000},"content-version":"unspecified","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":[[2018,6]]},"DOI":"10.1007\/s00037-016-0144-9","type":"journal-article","created":{"date-parts":[[2016,9,2]],"date-time":"2016-09-02T17:39:53Z","timestamp":1472837993000},"page":"305-350","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Matrix rigidity of random Toeplitz matrices"],"prefix":"10.1007","volume":"27","author":[{"given":"Oded","family":"Goldreich","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Avishay","family":"Tal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,9,1]]},"reference":[{"issue":"3","key":"144_CR1","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":"144_CR2","unstructured":"A. E. Andreev (1987). On a method for obtaining more than quadratic effective lower bounds for the complexity of \n\n$${\\pi}$$\n                        \n                            \n                                \u03c0\n                            \n                        \n                    -schemes. Moscow Univ. Math. Bull. 42, 63\u201366. In Russian."},{"issue":"3","key":"144_CR3","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1145\/990308.990311","volume":"51","author":"P. B\u00fcrgisser","year":"2004","unstructured":"B\u00fcrgisser P., Lotz M. (2004) Lower bounds on the bounded coefficient complexity of bilinear maps. J. ACM 51(3): 464\u2013482","journal-title":"J. ACM"},{"issue":"2","key":"144_CR4","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"},{"key":"144_CR5","doi-asserted-by":"crossref","unstructured":"O. Goldreich (2008). Computational Complexity: A Conceptual Perspective. Cambridge University Press.","DOI":"10.1017\/CBO9780511804106"},{"key":"144_CR6","doi-asserted-by":"crossref","unstructured":"O. Goldreich & A. Tal (2016). Matrix rigidity of random Toeplitz matrices. In STOC, 91\u2013104.","DOI":"10.1145\/2897518.2897633"},{"key":"144_CR7","unstructured":"O. Goldreich & A. Wigderson (2013). On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions. Electronic Colloquium on Computational Complexity (ECCC) 20, 43."},{"key":"144_CR8","unstructured":"J. H\u00e5stad (1989). Almost Optimal Lower Bounds for Small Depth Circuits. In RANDOMNESS AND COMPUTATION, 6\u201320. JAI Press."},{"key":"144_CR9","doi-asserted-by":"crossref","unstructured":"S. Kopparty, M. Kumar & M. E. Saks (2014). Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields. In ICALP, 726\u2013737.","DOI":"10.1007\/978-3-662-43948-7_60"},{"key":"144_CR10","unstructured":"R. Lidl & H. Niederreiter (1997). Finite Fields, volume 20 of Encyclopedia of mathematics and its applications. Cambridge University Press, 2nd edition."},{"issue":"1\u20132","key":"144_CR11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1561\/0400000011","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\u20132): 1\u2013155","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"issue":"1","key":"144_CR12","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1002\/rsa.20112","volume":"29","author":"E. Mossel","year":"2006","unstructured":"Mossel E., Shpilka A., Trevisan L. (2006) On epsilon-biased generators in \n\n$${NC^{0}}$$\n                        \n                            \n                                \n                                    N\n                                    \n                                        C\n                                        0\n                                    \n                                \n                            \n                        \n                    . Random Structures and Algorithms 29(1): 56\u201381","journal-title":"Random Structures and Algorithms"},{"issue":"4","key":"144_CR13","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"},{"issue":"3","key":"144_CR14","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1145\/1066100.1066101","volume":"52","author":"R. Paturi","year":"2005","unstructured":"Paturi R., Pudl\u00e1k P., Saks M.E., Zane F. (2005) An improved exponential-time algorithm for k-SAT. J. ACM 52(3): 337\u2013364","journal-title":"J. ACM"},{"key":"144_CR15","unstructured":"R. Paturi, P. Pudl\u00e1k & F. Zane (1999). Satisfiability Coding Lemma. Chicago J. Theor. Comput. Sci. 1999."},{"issue":"5","key":"144_CR16","doi-asserted-by":"crossref","first-page":"1356","DOI":"10.1137\/S0097539702402147","volume":"32","author":"R. Raz","year":"2003","unstructured":"Raz R. (2003) On the complexity of matrix product. SIAM J. on Computing 32(5): 1356\u20131369","journal-title":"SIAM J. on Computing"},{"issue":"6","key":"144_CR17","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 M.A., Stemann V. (1997) A Remark on Matrix Rigidity. Inf. Process. Lett. 64(6): 283\u2013285","journal-title":"Inf. Process. Lett."},{"key":"144_CR18","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\/article\/10.1007\/s00037-016-0144-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0144-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0144-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0144-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,5,18]],"date-time":"2018-05-18T14:10:00Z","timestamp":1526652600000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-016-0144-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9,1]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,6]]}},"alternative-id":["144"],"URL":"https:\/\/doi.org\/10.1007\/s00037-016-0144-9","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,9,1]]}}}