{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T05:43:55Z","timestamp":1772516635745,"version":"3.50.1"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2015,4,28]],"date-time":"2015-04-28T00:00:00Z","timestamp":1430179200000},"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":["Found Comput Math"],"published-print":{"date-parts":[[2016,6]]},"DOI":"10.1007\/s10208-015-9258-8","type":"journal-article","created":{"date-parts":[[2015,4,27]],"date-time":"2015-04-27T16:39:36Z","timestamp":1430152776000},"page":"599-635","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Complexity of Linear Circuits and Geometry"],"prefix":"10.1007","volume":"16","author":[{"given":"Fulvio","family":"Gesmundo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jonathan D.","family":"Hauenstein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Ikenmeyer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. M.","family":"Landsberg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,4,28]]},"reference":[{"key":"9258_CR1","unstructured":"Paolo Aluffi, Degrees of projections of rank loci, preprint arXiv:1408.1702 ."},{"key":"9258_CR2","doi-asserted-by":"crossref","unstructured":"E.\u00a0Arbarello, M.\u00a0Cornalba, P.\u00a0A. Griffiths, and J.\u00a0Harris, Geometry of algebraic curves. Vol. I, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 267, Springer-Verlag, New York, 1985.","DOI":"10.1007\/978-1-4757-5323-3"},{"issue":"1\u20133","key":"9258_CR3","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/S0024-3795(99)00225-6","volume":"304","author":"Bruno Codenotti","year":"2000","unstructured":"Bruno Codenotti, Matrix rigidity, Linear Algebra Appl. 304 (2000), no. 1\u20133, 181\u2013192.","journal-title":"Linear Algebra Appl."},{"key":"9258_CR4","unstructured":"Ronald de\u00a0Wolf, Lower bounds on matrix rigidity via a quantum argument, Automata, languages and programming. Part I, Lecture Notes in Comput. Sci., vol. 4051, Springer, Berlin, 2006, pp.\u00a062\u201371."},{"issue":"2","key":"9258_CR5","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1007\/s00037-011-0009-1","volume":"20","author":"Zeev Dvir","year":"2011","unstructured":"Zeev Dvir, On matrix rigidity and locally self-correctable codes, Comput. Complexity 20 (2011), no. 2, 367\u2013388.","journal-title":"Comput. Complexity"},{"issue":"2","key":"9258_CR6","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/BF01303207","volume":"13","author":"Joel Friedman","year":"1993","unstructured":"Joel Friedman, A note on matrix rigidity, Combinatorica 13 (1993), no. 2, 235\u2013239.","journal-title":"Combinatorica"},{"key":"9258_CR7","doi-asserted-by":"crossref","unstructured":"William Fulton, Intersection theory, second ed., Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics], vol.\u00a02, Springer-Verlag, Berlin, 1998.","DOI":"10.1007\/978-1-4612-1700-8"},{"key":"9258_CR8","unstructured":"William Fulton and Joe Harris, Representation theory, Graduate Texts in Mathematics, vol. 129, Springer-Verlag, New York, 1991, A first course, Readings in Mathematics."},{"key":"9258_CR9","doi-asserted-by":"crossref","unstructured":"Joe Harris, Algebraic geometry, Graduate Texts in Mathematics, vol. 133, Springer-Verlag, New York, 1995, A first course, Corrected reprint of the 1992 original.","DOI":"10.1007\/978-1-4757-2189-8"},{"issue":"4","key":"9258_CR10","doi-asserted-by":"crossref","first-page":"535","DOI":"10.4213\/mzm1314","volume":"63","author":"BS Kashin","year":"1998","unstructured":"B. S. Kashin and A. A. Razborov, New lower bounds for the stability of Hadamard matrices, Mat. Zametki 63 (1998), no. 4, 535\u2013540.","journal-title":"Mat. Zametki"},{"key":"9258_CR11","unstructured":"Abhinav Kumar, Satyanarayana\u00a0V. Lokam, Vijay\u00a0M. Patankar, and Jayalal Sarma M.\u00a0N., Using elimination theory to construct rigid matrices, Foundations of software technology and theoretical computer science\u2014FSTTCS 2009, LIPIcs. Leibniz Int. Proc. Inform., vol.\u00a04, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2009, pp.\u00a0299\u2013310."},{"key":"9258_CR12","volume-title":"Tensors: geometry and applications, Graduate Studies in Mathematics","author":"JM Landsberg","year":"2012","unstructured":"J. M. Landsberg, Tensors: geometry and applications, Graduate Studies in Mathematics, vol. 128, American Mathematical Society, Providence, RI, 2012."},{"key":"9258_CR13","unstructured":"J. M. Landsberg, J. Taylor, and N. K. Vishnoi, The geometry of matrix rigidity (preprint). https:\/\/smartech.gatech.edu\/handle\/1853\/6514 ."},{"key":"9258_CR14","unstructured":"F.\u00a0Thomson Leighton, Introduction to parallel algorithms and architectures, Morgan Kaufmann, San Mateo, CA, 1992, Arrays, trees, hypercubes."},{"issue":"1\u20132","key":"9258_CR15","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1016\/S0304-3975(00)00008-6","volume":"237","author":"Satyanarayana V Lokam","year":"2000","unstructured":"Satyanarayana\u00a0V. Lokam, On the rigidity of Vandermonde matrices, Theoret. Comput. Sci. 237 (2000), no.\u00a01-2, 477\u2013483.","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"9258_CR16","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1006\/jcss.2001.1786","volume":"63","author":"Satyanarayana V Lokam","year":"2001","unstructured":"Satyanarayana\u00a0V. Lokam, Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity, J. Comput. System Sci. 63 (2001), no.\u00a03, 449\u2013473.","journal-title":"J. Comput. System Sci."},{"key":"9258_CR17","unstructured":"Satyanarayana\u00a0V. Lokam, Quadratic lower bounds on matrix rigidity, Theory and applications of models of computation, Lecture Notes in Comput. Sci., vol. 3959, Springer, Berlin, 2006, pp.\u00a0295\u2013307."},{"key":"9258_CR18","doi-asserted-by":"crossref","unstructured":"Satyanarayana\u00a0V. Lokam, Complexity lower bounds using linear algebra, Found. Trends Theor. Comput. Sci. 4 (2008), no.\u00a01-2, front matter, 1\u2013155 (2009).","DOI":"10.1561\/0400000011"},{"issue":"5","key":"9258_CR19","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/j.ipl.2008.02.010","volume":"107","author":"Meena Mahajan","year":"2008","unstructured":"Meena Mahajan and Jayalal Sarma M.\u00a0N., Rigidity of a simple extended lower triangular matrix, Inform. Process. Lett. 107 (2008), no.\u00a05, 149\u2013153.","journal-title":"Inform. Process. Lett."},{"key":"9258_CR20","doi-asserted-by":"crossref","unstructured":"David Mumford, Algebraic geometry. I, Classics in Mathematics, Springer-Verlag, Berlin, 1995, Complex projective varieties, Reprint of the 1976 edition.","DOI":"10.1007\/978-3-642-61833-8_2"},{"key":"9258_CR21","doi-asserted-by":"crossref","unstructured":"David Mumford, The red book of varieties and schemes, expanded ed., Lecture Notes in Mathematics, vol. 1358, Springer-Verlag, Berlin, 1999, Includes the Michigan lectures (1974) on curves and their Jacobians, With contributions by Enrico Arbarello.","DOI":"10.1007\/978-3-540-46021-3_4"},{"issue":"2","key":"9258_CR22","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1137\/0206022","volume":"6","author":"Nicholas Pippenger","year":"1977","unstructured":"Nicholas Pippenger, Superconcentrators, SIAM J. Comput. 6 (1977), no. 2, 298\u2013304.","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9258_CR23","first-page":"213","volume":"32","author":"Pavel Pudl\u00e1k","year":"1991","unstructured":"Pavel Pudl\u00e1k and Zden\u011bk Vav\u0159\u00edn, Computation of rigidity of order $$n^2\/r$$ n 2 \/ r for one simple matrix, Comment. Math. Univ. Carolin. 32 (1991), no. 2, 213\u2013218.","journal-title":"Comment. Math. Univ. Carolin."},{"issue":"6","key":"9258_CR24","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1016\/S0020-0190(97)00190-7","volume":"64","author":"MA Shokrollahi","year":"1997","unstructured":"M. A. Shokrollahi, D. A. Spielman, and V. Stemann, A remark on matrix rigidity, Inform. Process. Lett. 64 (1997), no. 6, 283\u2013285.","journal-title":"Inform. Process. Lett."},{"key":"9258_CR25","unstructured":"Richard\u00a0P. Stanley, Enumerative combinatorics. Volume 1, second ed., Cambridge Studies in Advanced Mathematics, vol.\u00a049, Cambridge University Press, Cambridge, 2012."},{"issue":"3\u20134","key":"9258_CR26","first-page":"267","volume":"50","author":"Harry Tamvakis","year":"2004","unstructured":"Harry Tamvakis, The connection between representation theory and Schubert calculus, Enseign. Math 50 (2004), no.\u00a03-4, 267\u2013286.","journal-title":"Enseign. Math. (2)"},{"key":"9258_CR27","doi-asserted-by":"crossref","unstructured":"Leslie\u00a0G. Valiant, Graph-theoretic arguments in low-level complexity, Mathematical foundations of computer science (Proc. Sixth Sympos., Tatransk\u00e1 Lomnica, 1977), Springer, Berlin, 1977, pp. 162\u2013176. Lecture Notes in Comput. Sci., Vol. 53.","DOI":"10.1007\/3-540-08353-7_135"}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-015-9258-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10208-015-9258-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-015-9258-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,6]],"date-time":"2022-05-06T05:02:19Z","timestamp":1651813339000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10208-015-9258-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4,28]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,6]]}},"alternative-id":["9258"],"URL":"https:\/\/doi.org\/10.1007\/s10208-015-9258-8","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,4,28]]}}}