{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T03:20:58Z","timestamp":1648869658746},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,4,19]],"date-time":"2016-04-19T00:00:00Z","timestamp":1461024000000},"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":[[2016,6]]},"DOI":"10.1007\/s00037-016-0129-8","type":"journal-article","created":{"date-parts":[[2016,4,19]],"date-time":"2016-04-19T15:57:21Z","timestamp":1461081441000},"page":"309-348","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Kolmogorov Width of Discrete Linear Spaces: an Approach to Matrix Rigidity"],"prefix":"10.1007","volume":"25","author":[{"given":"Alex","family":"Samorodnitsky","sequence":"first","affiliation":[]},{"given":"Ilya","family":"Shkredov","sequence":"additional","affiliation":[]},{"given":"Sergey","family":"Yekhanin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,4,19]]},"reference":[{"key":"129_CR1","doi-asserted-by":"crossref","unstructured":"Michael Alekhnovich (2003). More on average case vs. approximation complexity. In 44th IEEE Symposium on Foundations of Computer Science (FOCS), 298\u2013307.","DOI":"10.1109\/SFCS.2003.1238204"},{"key":"129_CR2","doi-asserted-by":"crossref","unstructured":"Noga Alon & Gil Cohen (2013). On rigid matrices and U-polynomials. In 28th IEEE Computational Complexity Conference (CCC), 197\u2013206.","DOI":"10.1109\/CCC.2013.28"},{"key":"129_CR3","doi-asserted-by":"crossref","unstructured":"Noga Alon, Rina Panigrahy & Sergey Yekhanin (2009). Deterministic approximation algorithms for the nearest codeword problem. In 13th International Workshop on Randomization and Computation (RANDOM), volume 5687 of Lecture Notes in Computer Science, 339\u2013351.","DOI":"10.1007\/978-3-642-03685-9_26"},{"key":"129_CR4","volume-title":"Spectral Analysis of Large Dimensional Random Matrices","author":"Zhidong Bai","year":"2010","unstructured":"Bai Zhidong, Silverstein Jack (2010) Spectral Analysis of Large Dimensional Random Matrices. Springer, New York"},{"key":"129_CR5","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1007\/s00037-011-0009-1","volume":"20","author":"Zeev Dvir","year":"2011","unstructured":"Dvir Zeev (2011) On matrix rigidity and locally self-correctable codes. Computational Complexity 20: 367\u2013388","journal-title":"Computational Complexity"},{"key":"129_CR6","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/BF01303207","volume":"13","author":"Joel Friedman","year":"1993","unstructured":"Friedman Joel (1993) A note on matrix rigidity. Combinatorica 13: 235\u2013239","journal-title":"Combinatorica"},{"key":"129_CR7","first-page":"154","volume":"3","author":"Noboru Hamada","year":"1973","unstructured":"Hamada Noboru (1973) On the p-rank of the incidence matrix of a balanced or partially balanced incomplete block design and its applications to error-correcting codes. Hiroshima Mathematical Journal 3: 154\u2013226","journal-title":"Hiroshima Mathematical Journal"},{"key":"129_CR8","first-page":"32","volume":"2","author":"R. S. Ismagilov","year":"1968","unstructured":"Ismagilov R. S. (1968) n-dimensional width of compact in Hilbert space. Journal of Functional Analysis and Applications 2: 32\u201339","journal-title":"Journal of Functional Analysis and Applications"},{"key":"129_CR9","doi-asserted-by":"crossref","unstructured":"Stasys Jukna (2001). Extremal combinatorics. Springer, Berlin, Heidelberg, New York.","DOI":"10.1007\/978-3-662-04650-0"},{"key":"129_CR10","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/s10623-008-9249-8","volume":"51","author":"Dieter Jungnickel","year":"2009","unstructured":"Jungnickel Dieter, Tonchev Vladimir (2009) Polarities, quasi-symmetric designs, and Hamada conjecture. Designs, Codes, and Cryptography 51: 131\u2013140","journal-title":"Designs, Codes, and Cryptography"},{"key":"129_CR11","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1007\/BF02311250","volume":"63","author":"Boris Kashin","year":"1998","unstructured":"Kashin Boris, Razborov Alexander (1998) Improved lower bounds on the rigidity of Hadamard matrices. Mathematical Notes 63: 471\u2013475","journal-title":"Mathematical Notes"},{"key":"129_CR12","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1006\/jcss.2001.1786","volume":"63","author":"Satyanarayana Lokam","year":"2001","unstructured":"Lokam Satyanarayana (2001) Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity. Journal of Computer and System Sciences 63: 449\u2013473","journal-title":"Journal of Computer and System Sciences"},{"key":"129_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1561\/0400000011","volume":"4","author":"Satyanarayana Lokam","year":"2009","unstructured":"Lokam Satyanarayana (2009) Complexity lower bounds using linear algebra. Foundations and Trends in Theoretical Computer Science 4: 1\u2013155","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"129_CR14","unstructured":"F. J. MacWilliams & N. J. A. Sloane (1977). The Theory of Error Correcting Codes. North Holland, Amsterdam, New York."},{"key":"129_CR15","doi-asserted-by":"crossref","unstructured":"Ilan Newman & Yuri Rabinovich (2013). On multiplicative $${\\lambda}$$ \u03bb -approximations and some geometric applications. SIAM Journal on Computing 42, 885\u2013883.","DOI":"10.1137\/100801809"},{"key":"129_CR16","unstructured":"Alexander Razborov (1989). On rigid matrices. Manuscript. In Russian."},{"key":"129_CR17","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1006\/jcss.1997.1494","volume":"55","author":"Alexander Razborov","year":"1997","unstructured":"Razborov Alexander, Rudich Steven (1997) Natural proofs. Journal of Computer and System Sciences 55: 24\u201335","journal-title":"Journal of Computer and System Sciences"},{"key":"129_CR18","doi-asserted-by":"crossref","unstructured":"Shubhangi Saraf & Sergey Yekhanin (2011). Noisy interpolation of sparse polynomials, and applications. In 26th IEEE Computational Complexity Conference (CCC), 86\u201392.","DOI":"10.1109\/CCC.2011.38"},{"key":"129_CR19","unstructured":"Rocco Servedio & Emanuele Viola (2012). On a special case of rigidity. In Electronic Colloquium on Computational Complexity (ECCC), TR12-144."},{"key":"129_CR20","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1016\/S0020-0190(97)00190-7","volume":"64","author":"Amin Shokrollahi","year":"1997","unstructured":"Shokrollahi Amin, Spielman Daniel, Stemann Volker (1997) A remark on matrix rigidity. Information Processing Letters 64: 283\u2013285","journal-title":"Information Processing Letters"},{"key":"129_CR21","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1016\/S0021-9800(69)80046-3","volume":"7","author":"Kempton Smith","year":"1969","unstructured":"Smith Kempton (1969) On the p-rank of the incidence matrix of points and hyperplanes in a finite projective geometry. Journal of Combinatorial Theory 7: 122\u2013129","journal-title":"Journal of Combinatorial Theory"},{"key":"129_CR22","doi-asserted-by":"crossref","first-page":"785","DOI":"10.1007\/BF02312773","volume":"63","author":"Vladimir Temlyakov","year":"1998","unstructured":"Temlyakov Vladimir (1998) Nonlinear Kolmogorov widths. Mathematical Notes 63: 785\u2013795","journal-title":"Mathematical Notes"},{"key":"129_CR23","unstructured":"Kirill Uskov (2002). Kolmogorov width of geometric configurations and functional compacts in Hilbert spaces. Ph.D. thesis, Moscow State Technical University. In Russian."},{"key":"129_CR24","doi-asserted-by":"crossref","unstructured":"Leslie Valiant (1977). Graph-theoretic arguments in low level complexity. In 6th Symposium on Mathematical Foundations of Computer Science (MFCS), 162\u2013176.","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-016-0129-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-016-0129-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0129-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T15:01:59Z","timestamp":1558537319000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-016-0129-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,4,19]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,6]]}},"alternative-id":["129"],"URL":"https:\/\/doi.org\/10.1007\/s00037-016-0129-8","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,4,19]]}}}