{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:54:11Z","timestamp":1787316851268,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":35,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T00:00:00Z","timestamp":1529452800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,6,20]]},"DOI":"10.1145\/3188745.3188832","type":"proceedings-article","created":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T16:15:46Z","timestamp":1529511346000},"page":"1193-1206","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Generalized matrix completion and algebraic natural proofs"],"prefix":"10.1145","author":[{"given":"Markus","family":"Bl\u00e4ser","sequence":"first","affiliation":[{"name":"Saarland University, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christian","family":"Ikenmeyer","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Informatics, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gorav","family":"Jindal","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Informatics, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vladimir","family":"Lysikov","sequence":"additional","affiliation":[{"name":"Saarland University, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,6,20]]},"reference":[{"key":"e_1_3_2_2_1_1","volume-title":"Algebraic natural proofs theory is sought. Blog post at http:\/\/www.scottaaronson.com\/blog\/?p=336","author":"Aaronson Scott","year":"2008","unstructured":"Scott Aaronson and Andrew Drucker . Algebraic natural proofs theory is sought. Blog post at http:\/\/www.scottaaronson.com\/blog\/?p=336 , 2008 . Scott Aaronson and Andrew Drucker. Algebraic natural proofs theory is sought. Blog post at http:\/\/www.scottaaronson.com\/blog\/?p=336, 2008."},{"key":"e_1_3_2_2_2_1","volume-title":"Workshop on Complexity and Cryptography: Status of Impagliazzo\u2019s Worlds, Center for Computational Intractability","author":"Aaronson Scott","year":"2009","unstructured":"Scott Aaronson and Andrew Drucker . Impagliazzo\u2019s worlds in arithmetic complexity. Talk presented at the Workshop on Complexity and Cryptography: Status of Impagliazzo\u2019s Worlds, Center for Computational Intractability , Princeton, NJ , June 5, 2009 . Slides available at http:\/\/www.scottaaronson.com\/talks\/arith.ppt, 2009. Scott Aaronson and Andrew Drucker. Impagliazzo\u2019s worlds in arithmetic complexity. Talk presented at the Workshop on Complexity and Cryptography: Status of Impagliazzo\u2019s Worlds, Center for Computational Intractability, Princeton, NJ, June 5, 2009. Slides available at http:\/\/www.scottaaronson.com\/talks\/arith.ppt, 2009."},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/554706"},{"key":"e_1_3_2_2_4_1","first-page":"1","article-title":"Fast matrix multiplication. Theory of Computing","volume":"5","author":"Bl\u00e4ser Markus","year":"2013","unstructured":"Markus Bl\u00e4ser . Fast matrix multiplication. Theory of Computing , Graduate Surveys , 5 : 1 \u2013 60 , 2013 . Markus Bl\u00e4ser. Fast matrix multiplication. Theory of Computing, Graduate Surveys, 5:1\u201360, 2013.","journal-title":"Graduate Surveys"},{"key":"e_1_3_2_2_5_1","volume-title":"Introduction to geometric complexity theory. Lecture notes: https:\/\/people.mpiinf.mpg.de\/~cikenmey\/teaching\/ summer17\/introtogct\/gct.pdf","author":"Bl\u00e4ser Markus","year":"2017","unstructured":"Markus Bl\u00e4ser and Christian Ikenmeyer . Introduction to geometric complexity theory. Lecture notes: https:\/\/people.mpiinf.mpg.de\/~cikenmey\/teaching\/ summer17\/introtogct\/gct.pdf , 2017 . Markus Bl\u00e4ser and Christian Ikenmeyer. Introduction to geometric complexity theory. Lecture notes: https:\/\/people.mpiinf.mpg.de\/~cikenmey\/teaching\/ summer17\/introtogct\/gct.pdf, 2017."},{"key":"e_1_3_2_2_6_1","volume-title":"Completeness and Reduction in Algebraic Complexity Theory. Algorithms and Computation in Mathematics","author":"B\u00fcrgisser P.","year":"2000","unstructured":"P. B\u00fcrgisser . Completeness and Reduction in Algebraic Complexity Theory. Algorithms and Computation in Mathematics . Springer Berlin Heidelberg , 2000 . ISBN 9783540667520. P. B\u00fcrgisser. Completeness and Reduction in Algebraic Complexity Theory. Algorithms and Computation in Mathematics. Springer Berlin Heidelberg, 2000. ISBN 9783540667520."},{"key":"e_1_3_2_2_7_1","first-page":"150","volume-title":"Symposium on Theory of Computing Conference, STOC\u201913","author":"B\u00fcrgisser Peter","year":"2013","unstructured":"Peter B\u00fcrgisser and Christian Ikenmeyer . Explicit lower bounds via geometric complexity theory. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors , Symposium on Theory of Computing Conference, STOC\u201913 , Palo Alto, CA, USA , June 1-4, 2013 , pages 141\u2013 150 . ACM, 2013. ISBN 978-1-4503-2029-0. Peter B\u00fcrgisser and Christian Ikenmeyer. Explicit lower bounds via geometric complexity theory. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC\u201913, Palo Alto, CA, USA, June 1-4, 2013, pages 141\u2013150. ACM, 2013. ISBN 978-1-4503-2029-0."},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03338-8"},{"key":"e_1_3_2_2_9_1","volume-title":"On the equivalence between low rank matrix completion and tensor rank. CoRR, abs\/1406.0080","author":"Derksen Harm","year":"2014","unstructured":"Harm Derksen . On the equivalence between low rank matrix completion and tensor rank. CoRR, abs\/1406.0080 , 2014 . Harm Derksen. On the equivalence between low rank matrix completion and tensor rank. CoRR, abs\/1406.0080, 2014."},{"key":"e_1_3_2_2_10_1","volume-title":"Rafael Mendes de Oliveira, and Avi Wigderson. Barriers for rank methods in arithmetic complexity. CoRR, abs\/1710.09502","author":"Efremenko Klim","year":"2017","unstructured":"Klim Efremenko , Ankit Garg , Rafael Mendes de Oliveira, and Avi Wigderson. Barriers for rank methods in arithmetic complexity. CoRR, abs\/1710.09502 , 2017 . Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira, and Avi Wigderson. Barriers for rank methods in arithmetic complexity. CoRR, abs\/1710.09502, 2017."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055496"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40313-2_39"},{"key":"e_1_3_2_2_13_1","series-title":"London Mathematical Society Student Texts","volume-title":"Young tableaux","author":"Fulton William","year":"1997","unstructured":"William Fulton . Young tableaux , volume 35 of London Mathematical Society Student Texts . Cambridge University Press , Cambridge , 1997 . ISBN 0-521-56144-2; 0-521-56724-6. William Fulton. Young tableaux, volume 35 of London Mathematical Society Student Texts. Cambridge University Press, Cambridge, 1997. ISBN 0-521-56144-2; 0-521-56724-6."},{"key":"e_1_3_2_2_14_1","series-title":"Graduate Texts in Mathematics","volume-title":"Representation Theory - A First Course","author":"Fulton William","year":"1991","unstructured":"William Fulton and Joe Harris . Representation Theory - A First Course , volume 129 of Graduate Texts in Mathematics . Springer , 1991 . William Fulton and Joe Harris. Representation Theory - A First Course, volume 129 of Graduate Texts in Mathematics. Springer, 1991."},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1216\/RMJ-1976-6-3-449"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.20"},{"key":"e_1_3_2_2_17_1","first-page":"14","volume-title":"43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016","volume":"55","author":"Grochow Joshua A.","year":"2016","unstructured":"Joshua A. Grochow , Ketan D. Mulmuley , and Youming Qiao . Boundaries of VP and VNP. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors , 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016 , July 11-15, 2016 , Rome, Italy , volume 55 of LIPIcs, pages 34:1\u201334: 14 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. ISBN 978-3-95977-013-2. Joshua A. Grochow, Ketan D. Mulmuley, and Youming Qiao. Boundaries of VP and VNP. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 34:1\u201334:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. ISBN 978-3-95977-013-2."},{"key":"e_1_3_2_2_18_1","volume-title":"Towards an algebraic natural proofs barrier via polynomial identity testing. CoRR, abs\/1701.01717","author":"Grochow Joshua A.","year":"2017","unstructured":"Joshua A. Grochow , Mrinal Kumar , Michael E. Saks , and Shubhangi Saraf . Towards an algebraic natural proofs barrier via polynomial identity testing. CoRR, abs\/1701.01717 , 2017 . Joshua A. Grochow, Mrinal Kumar, Michael E. Saks, and Shubhangi Saraf. Towards an algebraic natural proofs barrier via polynomial identity testing. CoRR, abs\/1701.01717, 2017."},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055440"},{"key":"e_1_3_2_2_20_1","series-title":"JMLR Workshop and Conference Proceedings","first-page":"725","volume-title":"Proceedings of The 27th Conference on Learning Theory, COLT","author":"Hardt Moritz","year":"2014","unstructured":"Moritz Hardt , Raghu Meka , Prasad Raghavendra , and Benjamin Weitz . Computational limits for matrix completion . In Maria-Florina Balcan, Vitaly Feldman, and Csaba Szepesv\u00e1ri, editors, Proceedings of The 27th Conference on Learning Theory, COLT 2014 , Barcelona , Spain, June 13-15, 2014, volume 35 of JMLR Workshop and Conference Proceedings , pages 703\u2013 725 . JMLR.org, 2014. Moritz Hardt, Raghu Meka, Prasad Raghavendra, and Benjamin Weitz. Computational limits for matrix completion. In Maria-Florina Balcan, Vitaly Feldman, and Csaba Szepesv\u00e1ri, editors, Proceedings of The 27th Conference on Learning Theory, COLT 2014, Barcelona, Spain, June 13-15, 2014, volume 35 of JMLR Workshop and Conference Proceedings, pages 703\u2013725. JMLR.org, 2014."},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109679"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90014-6"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0182-6"},{"key":"e_1_3_2_2_25_1","first-page":"412","volume-title":"Randomness and Computation","author":"Kaltofen Erich","unstructured":"Erich Kaltofen . Factorization of polynomials given by straight-line programs . In Randomness and Computation , pages 375\u2013 412 . JAI Press, 1989. Erich Kaltofen. Factorization of polynomials given by straight-line programs. In Randomness and Computation, pages 375\u2013412. JAI Press, 1989."},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2006.09.006"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/080718115"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2184319.2184341"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970038715X"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01261326"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1494"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-6804-6"},{"key":"e_1_3_2_2_33_1","volume-title":"The complexity of tensor rank. CoRR, abs\/1612.04338","author":"Schaefer Marcus","year":"2016","unstructured":"Marcus Schaefer and Daniel Stefankovic . The complexity of tensor rank. CoRR, abs\/1612.04338 , 2016 . Marcus Schaefer and Daniel Stefankovic. The complexity of tensor rank. CoRR, abs\/1612.04338, 2016."},{"key":"e_1_3_2_2_34_1","volume-title":"How hard is the tensor rank? CoRR, abs\/1611.01559","author":"Shitov Yarolav","year":"2016","unstructured":"Yarolav Shitov . How hard is the tensor rank? CoRR, abs\/1611.01559 , 2016 . Yarolav Shitov. How hard is the tensor rank? CoRR, abs\/1611.01559, 2016."},{"key":"e_1_3_2_2_35_1","volume-title":"Relative error tensor low rank approximation. CoRR, abs\/1704.08246","author":"Song Zhao","year":"2017","unstructured":"Zhao Song , David P. Woodruff , and Peilin Zhong . Relative error tensor low rank approximation. CoRR, abs\/1704.08246 , 2017 . Zhao Song, David P. Woodruff, and Peilin Zhong. Relative error tensor low rank approximation. CoRR, abs\/1704.08246, 2017."}],"event":{"name":"STOC '18: Symposium on Theory of Computing","location":"Los Angeles CA USA","acronym":"STOC '18","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188832","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188832","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:07:09Z","timestamp":1750198029000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188832"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,20]]},"references-count":35,"alternative-id":["10.1145\/3188745.3188832","10.1145\/3188745"],"URL":"https:\/\/doi.org\/10.1145\/3188745.3188832","relation":{},"subject":[],"published":{"date-parts":[[2018,6,20]]},"assertion":[{"value":"2018-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}