{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,9,22]],"date-time":"2022-09-22T02:21:14Z","timestamp":1663813274022},"reference-count":64,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,4,2]],"date-time":"2021-04-02T00:00:00Z","timestamp":1617321600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,4,2]],"date-time":"2021-04-02T00:00:00Z","timestamp":1617321600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2021,6]]},"DOI":"10.1007\/s00037-021-00205-2","type":"journal-article","created":{"date-parts":[[2021,4,2]],"date-time":"2021-04-02T18:02:21Z","timestamp":1617386541000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Lower Bounds for Matrix Factorization"],"prefix":"10.1007","volume":"30","author":[{"given":"Ben Lee","family":"Volk","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mrinal","family":"Kumar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,4,2]]},"reference":[{"key":"205_CR1","doi-asserted-by":"crossref","unstructured":"Manindra Agrawal (2005). Proving Lower Bounds Via Pseudo-random Generators. In Proceedings of the 25th International Conference\non Foundations of Software Technology and Theoretical Computer\nScience (FSTTCS 2005),, 92\u2013105. URL https:\/\/doi.org\/10.1007\/11590156_6","DOI":"10.1007\/11590156_6"},{"key":"205_CR2","doi-asserted-by":"crossref","unstructured":"Manindra Agrawal, Rohit Gurjar, Arpita Korwar & Nitin Saxena (2015). Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits. SIAM J. Comput. 44(3), 669\u2013697. URL https:\/\/doi.org\/10.1137\/140975103","DOI":"10.1137\/140975103"},{"key":"#cr-split#-205_CR3.1","doi-asserted-by":"crossref","unstructured":"Manindra Agrawal & V.\u00a0Vinay (2008). Arithmetic Circuits: A Chasm at Depth Four. In Proceedings of the 49th Annual IEEE Symposium","DOI":"10.1109\/FOCS.2008.32"},{"key":"#cr-split#-205_CR3.2","doi-asserted-by":"crossref","unstructured":"on Foundations of Computer Science (FOCS 2008),, 67-75. URL https:\/\/doi.org\/10.1109\/FOCS.2008.32","DOI":"10.1109\/FOCS.2008.32"},{"key":"#cr-split#-205_CR4.1","doi-asserted-by":"crossref","unstructured":"Josh Alman & Lijie Chen (2019). Efficient Construction of Rigid Matrices Using an NP Oracle. InProceedings of the 60th Annual IEEE","DOI":"10.1109\/FOCS.2019.00067"},{"key":"#cr-split#-205_CR4.2","doi-asserted-by":"crossref","unstructured":"Symposium on Foundations of Computer Science (FOCS 2019), 1034-1055. IEEE Computer Society. URL https:\/\/doi.org\/10.1109\/FOCS.2019.00067","DOI":"10.1109\/FOCS.2019.00067"},{"key":"#cr-split#-205_CR5.1","doi-asserted-by":"crossref","unstructured":"Josh Alman & R.\u00a0Ryan Williams (2017). Probabilistic rank and matrix rigidity. In Proceedings of the 49th Annual ACM Symposium on","DOI":"10.1145\/3055399.3055484"},{"key":"#cr-split#-205_CR5.2","doi-asserted-by":"crossref","unstructured":"Theory of Computing (STOC 2017),, 641-652. ACM. URL https:\/\/doi.org\/10.1145\/3055399.3055484","DOI":"10.1145\/3055399.3055484"},{"key":"205_CR6","doi-asserted-by":"crossref","unstructured":"Noga Alon & Pavel Pudl\u00e1k (1994). Superconcentrators of Depths 2 and 3; Odd Levels Help (Rarely). J. Comput. Syst. Sci. 48(1), 194\u2013202. URL https:\/\/doi.org\/10.1016\/S0022-0000(05)80027-3","DOI":"10.1016\/S0022-0000(05)80027-3"},{"key":"205_CR7","doi-asserted-by":"crossref","unstructured":"Bruce Anderson, Jeffrey Jackson & Meera Sitharam (1998). Descartes' rule of signs revisited. Amer. Math. Monthly 105(5), 447\u2013451. ISSN 0002-9890. URL https:\/\/doi.org\/10.2307\/3109807","DOI":"10.1080\/00029890.1998.12004907"},{"key":"205_CR8","doi-asserted-by":"crossref","unstructured":"Walter Baur & Volker Strassen (1983). The Complexity of Partial Derivatives. Theoretical Computer Science 22, 317\u2013330. URL https:\/\/doi.org\/10.1016\/0304-3975(83)90110-X","DOI":"10.1016\/0304-3975(83)90110-X"},{"key":"#cr-split#-205_CR9.1","doi-asserted-by":"crossref","unstructured":"Avraham Ben-Aroya, Dean Doron & Amnon Ta-Shma (2017). An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy. In Proceedings of the 49th Annual","DOI":"10.1145\/3055399.3055423"},{"key":"#cr-split#-205_CR9.2","doi-asserted-by":"crossref","unstructured":"ACM Symposium on Theory of Computing (STOC 2017),, 1185-1194. ACM. URL https:\/\/doi.org\/10.1145\/3055399.3055423","DOI":"10.1145\/3055399.3055423"},{"key":"#cr-split#-205_CR10.1","doi-asserted-by":"crossref","unstructured":"Amey Bhangale, Prahladh Harsha, Orr Paradise & Avishay Tal (2020). Rigid Matrices From Rectangular PCPs or: Hard Claims Have Complex Proofs. In Proceedings of the 61st Annual IEEE Symposium","DOI":"10.1109\/FOCS46700.2020.00084"},{"key":"#cr-split#-205_CR10.2","doi-asserted-by":"crossref","unstructured":"on Foundations of Computer Science (FOCS 2020),, 858-869. URL https:\/\/doi.org\/10.1109\/FOCS46700.2020.00084","DOI":"10.1109\/FOCS46700.2020.00084"},{"key":"205_CR11","doi-asserted-by":"crossref","unstructured":"Nader\u00a0H. Bshouty (2014). Testers and their applications. In Innovations in Theoretical Computer Science, ITCS'14, 2014, 327\u2013352. URL https:\/\/doi.org\/10.1145\/2554797.2554828","DOI":"10.1145\/2554797.2554828"},{"key":"205_CR12","doi-asserted-by":"crossref","unstructured":"Peter B\u00fcrgisser, Michael Clausen & Mohammad\u00a0A. Shokrollahi (1997). Algebraic Complexity Theory, volume 315 of Grundlehren der mathematischen Wissenschaften. Springer-Verlag. URL https:\/\/doi.org\/10.1007\/978-3-662-03338-8","DOI":"10.1007\/978-3-662-03338-8"},{"key":"205_CR13","doi-asserted-by":"crossref","unstructured":"Eshan Chattopadhyay & David Zuckerman (2019). Explicit two-source extractors and resilient functions. Ann. of Math. (2) 189(3), 653\u2013705. ISSN 0003-486X. URL https:\/\/doi.org\/10.4007\/annals.2019.189.3.1","DOI":"10.4007\/annals.2019.189.3.1"},{"key":"205_CR14","unstructured":"Bernard Chazelle (2001). The discrepancy method - randomness and complexity. Cambridge University Press. ISBN 978-0-521-00357-5. URL https:\/\/www.cs.princeton.edu\/~chazelle\/pubs\/book.pdf"},{"key":"205_CR15","doi-asserted-by":"crossref","unstructured":"Gil Cohen (2017). Towards optimal two-source extractors and Ramsey graphs. In \nProceedings of the 49th Annual ACM Symposium on Theory\nof Computing (STOC 2017),, 1157\u20131170. ACM. URL https:\/\/doi.org\/10.1145\/3055399.3055429","DOI":"10.1145\/3055399.3055429"},{"key":"#cr-split#-205_CR16.1","doi-asserted-by":"crossref","unstructured":"Danny Dolev, Cynthia Dwork, Nicholas Pippenger & Avi Wigderson (1983). Superconcentrators, Generalizers and Generalized Connectors with Limited Depth (Preliminary Version). In","DOI":"10.1145\/800061.808731"},{"key":"#cr-split#-205_CR16.2","doi-asserted-by":"crossref","unstructured":"Proceedings of the 15th Annual ACM Symposium on Theory of Computing (STOC 1983),, 42-51. ACM. https:\/\/doi.org\/10.1145\/800061.808731","DOI":"10.1145\/800061.808731"},{"key":"205_CR17","doi-asserted-by":"crossref","unstructured":"Zeev Dvir & Benjamin\u00a0L. Edelman (2019). Matrix Rigidity and the Croot-Lev-Pach Lemma. Theory Comput. 15, 1\u20137. URL https:\/\/doi.org\/10.4086\/toc.2019.v015a008","DOI":"10.4086\/toc.2019.v015a008"},{"key":"#cr-split#-205_CR18.1","doi-asserted-by":"crossref","unstructured":"Zeev Dvir, Alexander Golovnev & Omri Weinstein (2019). Static data structure lower bounds imply rigidity. In Proceedings of the","DOI":"10.1145\/3313276.3316348"},{"key":"#cr-split#-205_CR18.2","doi-asserted-by":"crossref","unstructured":"51st Annual ACM Symposium on Theory of Computing (STOC 2019),, 967-978. ACM. URL https:\/\/doi.org\/10.1145\/3313276.3316348","DOI":"10.1145\/3313276.3316348"},{"key":"205_CR19","doi-asserted-by":"crossref","unstructured":"Zeev Dvir & Allen Liu (2020). Fourier and Circulant Matrices are Not Rigid. Theory Comput. 16, 1\u201348. URL https:\/\/doi.org\/10.4086\/toc.2020.v016a020","DOI":"10.4086\/toc.2020.v016a020"},{"key":"205_CR20","doi-asserted-by":"crossref","unstructured":"Michael\u00a0A. Forbes & Amir Shpilka (2012). On identity testing of tensors, low-rank recovery and compressed sensing. In Proceedings\nof the 44th Annual ACM Symposium on Theory of Computing (STOC\n2012),, Howard\u00a0J. Karloff & Toniann Pitassi, editors, 163\u2013172. ACM. URL https:\/\/doi.org\/10.1145\/2213977.2213995","DOI":"10.1145\/2213977.2213995"},{"key":"205_CR21","doi-asserted-by":"crossref","unstructured":"Michael\u00a0L. Fredman (1982). The Complexity of Maintaining an Array and Computing Its Partial Sums. J. ACM 29(1), 250\u2013260. URL https:\/\/doi.org\/10.1145\/322290.322305","DOI":"10.1145\/322290.322305"},{"key":"205_CR22","doi-asserted-by":"crossref","unstructured":"Michael\u00a0L. Fredman & Michael\u00a0E. Saks (1989). The Cell Probe Complexity of Dynamic Data Structures. In \nProceedings of the 21st\nAnnual ACM Symposium on Theory of Computing (STOC 1989),, David\u00a0S. Johnson, editor, 345\u2013354. ACM. URL https:\/\/doi.org\/10.1145\/73007.73040","DOI":"10.1145\/73007.73040"},{"key":"205_CR23","doi-asserted-by":"crossref","unstructured":"Joel Friedman (1993). A note on matrix rigidity. Combinatorica 13(2), 235\u2013239. URL https:\/\/doi.org\/10.1007\/BF01303207","DOI":"10.1007\/BF01303207"},{"key":"205_CR24","doi-asserted-by":"crossref","unstructured":"Anna G\u00e1l, Kristoffer\u00a0Arnsfelt Hansen, Michal Kouck\u00fd, Pavel Pudl\u00e1k & Emanuele Viola (2013). Tight Bounds on Computing Error-Correcting Codes by Bounded-Depth Circuits With Arbitrary Gates. IEEE Trans. Information Theory 59(10), 6611\u20136627. URL https:\/\/doi.org\/10.1109\/TIT.2013.2270275","DOI":"10.1109\/TIT.2013.2270275"},{"key":"205_CR25","doi-asserted-by":"crossref","unstructured":"Ankit Gupta, Pritish Kamath, Neeraj Kayal & Ramprasad Saptharishi (2016). Arithmetic Circuits: A Chasm at Depth 3. SIAM J. Comput. 45(3), 1064\u20131079. URL https:\/\/doi.org\/10.1137\/140957123","DOI":"10.1137\/140957123"},{"key":"205_CR26","unstructured":"Venkatesan Guruswami, Atri Rudra & Madhu Sudan (2018). Essential Coding Theory. URL https:\/\/cse.buffalo.edu\/faculty\/atri\/courses\/coding-theory\/book\/"},{"key":"205_CR27","doi-asserted-by":"crossref","unstructured":"Joos Heintz & Claus-Peter Schnorr (1980). Testing Polynomials which Are Easy to Compute (Extended Abstract). In \nProceedings of the\n12th Annual ACM Symposium on Theory of Computing (STOC 1980),, 262\u2013272. URL https:\/\/doi.org\/10.1145\/800141.804674","DOI":"10.1145\/800141.804674"},{"key":"205_CR28","doi-asserted-by":"crossref","unstructured":"Stasys Jukna & Igor Sergeev (2013). Complexity of Linear Boolean Operators. Foundations and Trends in Theoretical Computer Science 9(1), 1\u2013123. ISSN 1551-305X. URL https:\/\/doi.org\/10.1561\/0400000063","DOI":"10.1561\/0400000063"},{"key":"205_CR29","unstructured":"Erich Kaltofen & Michael\u00a0F. Singer (1991). Size efficient parallel algebraic circuits for partial derivatives. In IV International Conference on Computer Algebra in Physical Research, 133\u2013145. URL https:\/\/users.cs.duke.edu\/~elk27\/bibliography\/91\/KaSi91.pdf"},{"key":"205_CR30","doi-asserted-by":"crossref","unstructured":"Pascal Koiran (2012). Arithmetic Circuits: The Chasm at Depth Four Gets Wider. Theoretical Computer Science 448, 56\u201365. URL https:\/\/doi.org\/10.1016\/j.tcs.2012.03.041","DOI":"10.1016\/j.tcs.2012.03.041"},{"key":"205_CR31","unstructured":"Mrinal Kumar & Ben\u00a0Lee Volk (2020). Lower Bounds for Matrix Factorization. In \nProceedings of the 35th Annual Computational Complexity\nConference (CCC 2020),, volume 169, 5:1\u20135:20. URL https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2020.5"},{"key":"205_CR32","doi-asserted-by":"crossref","unstructured":"Kasper\u00a0Green Larsen (2012). The cell probe complexity of dynamic range counting. In \nProceedings of the 44th Annual ACM Symposium on\nTheory of Computing (STOC 2012),, 85\u201394. ACM. URL https:\/\/doi.org\/10.1145\/2213977.2213987","DOI":"10.1145\/2213977.2213987"},{"key":"205_CR33","doi-asserted-by":"crossref","unstructured":"Kasper\u00a0Green Larsen (2014). On Range Searching in the Group Model and Combinatorial Discrepancy. SIAM J. Comput. 43(2), 673\u2013686. URL https:\/\/doi.org\/10.1137\/120865240","DOI":"10.1137\/120865240"},{"key":"205_CR34","doi-asserted-by":"crossref","unstructured":"Kasper\u00a0Green Larsen, Omri Weinstein & Huacheng Yu (2018). Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds. In \nProceedings of the 50th Annual ACM Symposium on\nTheory of Computing (STOC 2018),, 978\u2013989. ACM. URL https:\/\/doi.org\/10.1145\/3188745.3188790","DOI":"10.1145\/3188745.3188790"},{"key":"205_CR35","unstructured":"Daniel\u00a0D. Lee & H.\u00a0Sebastian Seung (2000). Algorithms for Non-negative Matrix Factorization. In Advances in Neural Information Processing Systems 13, Papers from Neural Information Processing Systems (NIPS) 2000, 556\u2013562. MIT Press. URL http:\/\/proceedings.neurips.cc\/paper\/1861-algorithms-for-non-negative-matrix-factorization"},{"key":"205_CR36","unstructured":"Xin Li (2019). Non-Malleable Extractors and Non-Malleable Codes: Partially Optimal Constructions. In \nProceedings of the 34th Annual\nComputational Complexity Conference (CCC 2019),, volume 137, 28:1\u201328:49. URL https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2019.28"},{"key":"205_CR37","doi-asserted-by":"crossref","unstructured":"Satyanarayana\u00a0V. Lokam (2009). Complexity Lower Bounds using Linear Algebra. Foundations and Trends in Theoretical Computer Science 4(1-2), 1\u2013155. URL https:\/\/doi.org\/10.1561\/0400000011","DOI":"10.1561\/0400000011"},{"key":"205_CR38","doi-asserted-by":"crossref","unstructured":"Julien Mairal, Francis\u00a0R. Bach, Jean Ponce & Guillermo Sapiro (2009). Online dictionary learning for sparse coding. In Proceedings of the 26th Annual International Conference on Machine Learning, ICML 2009, volume 382 of ACM International Conference Proceeding Series, 689\u2013696. ACM. URL https:\/\/doi.org\/10.1145\/1553374.1553463","DOI":"10.1145\/1553374.1553463"},{"key":"205_CR39","doi-asserted-by":"crossref","unstructured":"Jacques Morgenstern (1973). Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform. J. ACM 20(2), 305\u2013306. URL https:\/\/doi.org\/10.1145\/321752.321761","DOI":"10.1145\/321752.321761"},{"key":"205_CR40","unstructured":"Behnam Neyshabur & Rina Panigrahy (2013). Sparse Matrix Factorization. CoRR abs\/1311.3315. URL http:\/\/arxiv.org\/abs\/1311.3315"},{"key":"205_CR41","doi-asserted-by":"crossref","unstructured":"Mihai P\u01cetra\u015fcu (2007). Lower bounds for 2-dimensional range counting. In \nProceedings of the 39th Annual ACM Symposium on Theory of\nComputing (STOC 2007),, 40\u201346. ACM. URL https:\/\/doi.org\/10.1145\/1250790.1250797","DOI":"10.1145\/1250790.1250797"},{"key":"205_CR42","doi-asserted-by":"crossref","unstructured":"Mihai P\u01cetra\u015fcu & Erik\u00a0D. Demaine (2006). Logarithmic Lower Bounds in the Cell-Probe Model. SIAM J. Comput. 35(4), 932\u2013963. URL https:\/\/doi.org\/10.1137\/S0097539705447256","DOI":"10.1137\/S0097539705447256"},{"key":"205_CR43","doi-asserted-by":"crossref","unstructured":"Nicholas Pippenger (1977). Superconcentrators. SIAM J. Comput. 6(2), 298\u2013304. URL https:\/\/doi.org\/10.1137\/0206022","DOI":"10.1137\/0206022"},{"key":"205_CR44","doi-asserted-by":"crossref","unstructured":"Nicholas Pippenger (1982). Superconcentrators of Depth 2. J. Comput. Syst. Sci. 24(1), 82\u201390. URL https:\/\/doi.org\/10.1016\/0022-0000(82)90056-3","DOI":"10.1016\/0022-0000(82)90056-3"},{"key":"205_CR45","doi-asserted-by":"crossref","unstructured":"Pavel Pudl\u00e1k (1994). Communication in Bounded Depth Circuits. Combinatorica 14(2), 203\u2013216. URL https:\/\/doi.org\/10.1007\/BF01215351","DOI":"10.1007\/BF01215351"},{"key":"205_CR46","doi-asserted-by":"crossref","unstructured":"Pavel Pudl\u00e1k (2000). A note on the use of determinant for proving lower bounds on the size of linear circuits. Inf. Process. Lett. 74(5-6), 197\u2013201. URL https:\/\/doi.org\/10.1016\/S0020-0190(00)00058-2","DOI":"10.1016\/S0020-0190(00)00058-2"},{"key":"205_CR47","doi-asserted-by":"crossref","unstructured":"Jaikumar Radhakrishnan & Amnon Ta-Shma (2000). Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators. SIAM J. Discrete Math. 13(1), 2\u201324. URL https:\/\/doi.org\/10.1137\/S0895480197329508","DOI":"10.1137\/S0895480197329508"},{"key":"205_CR48","doi-asserted-by":"crossref","unstructured":"Ran Raz (2010). Elusive Functions and Lower Bounds for Arithmetic Circuits. Theory of Computing 6(1), 135\u2013177. URL https:\/\/doi.org\/10.4086\/toc.2010.v006a007","DOI":"10.4086\/toc.2010.v006a007"},{"key":"205_CR49","doi-asserted-by":"crossref","unstructured":"Ran Raz & Amir Shpilka (2003). Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates. SIAM J. Comput. 32(2), 488\u2013513. URL https:\/\/doi.org\/10.1137\/S009753970138462X","DOI":"10.1137\/S009753970138462X"},{"key":"205_CR50","doi-asserted-by":"crossref","unstructured":"Mohammad\u00a0Amin Shokrollahi, Daniel\u00a0A. Spielman & Volker Stemann (1997). A Remark on Matrix Rigidity. Inf. Process. Lett. 64(6), 283\u2013285. URL https:\/\/doi.org\/10.1016\/S0020-0190(97)00190-7","DOI":"10.1016\/S0020-0190(97)00190-7"},{"key":"205_CR51","doi-asserted-by":"crossref","unstructured":"Victor Shoup (1990). New Algorithms for Finding Irreducible Polynomials over Finite Fields. Mathematics of Computation 54, 435\u2013447. URL https:\/\/www.ams.org\/journals\/mcom\/1990-54-189\/S0025-5718-1990-0993933-0\/S0025-5718-1990-0993933-0.pdf","DOI":"10.1090\/S0025-5718-1990-0993933-0"},{"key":"205_CR52","doi-asserted-by":"crossref","unstructured":"Victor Shoup & Roman Smolensky (1996). Lower bounds for polynomial evaluation and interpolation problems. Computational Complexity 6(4), 301\u2013311. URL https:\/\/doi.org\/10.1007\/BF01270384","DOI":"10.1007\/BF01270384"},{"key":"205_CR53","doi-asserted-by":"crossref","unstructured":"Amir Shpilka & Amir Yehudayoff (2010). Arithmetic Circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science 5, 207\u2013388. ISSN 1551-305X. URL https:\/\/doi.org\/10.1561\/0400000039","DOI":"10.1561\/0400000039"},{"key":"205_CR54","doi-asserted-by":"crossref","unstructured":"Volker Strassen (1973). Die Berechnungskomplexit\u00e4t Von Elementarsymmetrischen Funktionen Und Von Interpolationskoeffizienten. Numerische Mathematik 20(3), 238\u2013251. ISSN 0029-599X. URL https:\/\/doi.org\/10.1007\/BF01436566","DOI":"10.1007\/BF01436566"},{"key":"205_CR55","doi-asserted-by":"crossref","unstructured":"S\u00e9bastien Tavenas (2015). Improved bounds for reduction to depth 4 and depth 3. Inf. Comput. 240, 2\u201311. URL https:\/\/doi.org\/10.1016\/j.ic.2014.09.004. 2013","DOI":"10.1016\/j.ic.2014.09.004"},{"key":"205_CR56","doi-asserted-by":"crossref","unstructured":"Leslie\u00a0G. Valiant (1975). On Non-linear Lower Bounds in Computational Complexity. In \nProceedings of the 7th Annual ACM Symposium\non Theory of Computing (STOC 1975),, 45\u201353. ACM. URL http:\/\/doi.acm.org\/10.1145\/800116.803752","DOI":"10.1145\/800116.803752"},{"key":"205_CR57","doi-asserted-by":"crossref","unstructured":"Leslie\u00a0G. Valiant (1977). Graph-Theoretic Arguments in Low-Level Complexity. In \nProceedings of the 2nd Internationl Symposium on the\nMathematical Foundations of Computer Science (MFCS 1977),, volume\u00a053 of Lecture Notes in Computer Science, 162\u2013176. Springer. URL https:\/\/doi.org\/10.1007\/3-540-08353-7_135","DOI":"10.1007\/3-540-08353-7_135"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-021-00205-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-021-00205-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-021-00205-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,29]],"date-time":"2021-06-29T03:59:02Z","timestamp":1624939142000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-021-00205-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,2]]},"references-count":64,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["205"],"URL":"https:\/\/doi.org\/10.1007\/s00037-021-00205-2","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,2]]},"assertion":[{"value":"31 July 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 April 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"6"}}