{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:41:40Z","timestamp":1781077300993,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":41,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["DMS-1802059, DMS-1851420, DMS-1953141"],"award-info":[{"award-number":["DMS-1802059, DMS-1851420, DMS-1953141"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451007","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"800-808","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Structure vs. randomness for bilinear maps"],"prefix":"10.1145","author":[{"given":"Alex","family":"Cohen","sequence":"first","affiliation":[{"name":"Yale University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guy","family":"Moshkovitz","sequence":"additional","affiliation":[{"name":"City University of New York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"K. Adiprasito D. Kazhdan and T. Zieglar On the Schmidt and analytic ranks for trilinear forms arXiv:2102.03659 ( 2021 )."},{"key":"e_1_3_2_1_2_1","volume-title":"A refined Laser Method and faster matrix multiplication, arXiv","author":"Alman J.","year":"2010","unstructured":"J. Alman and V. V. Williams, A refined Laser Method and faster matrix multiplication, arXiv: 2010. 05846 ( 2020 )."},{"key":"e_1_3_2_1_3_1","first-page":"253","volume":"31","author":"Atkinson M. D.","unstructured":"M. D. Atkinson and S. Lloyd, Large spaces of matrices of bounded rank, Q. J. Math. 31 ( 1980 ), 253-262.","journal-title":"J. Math."},{"key":"e_1_3_2_1_4_1","unstructured":"A. Bhowmick and S. Lovett Bias vs structure of polynomials in large fields and applications in efective algebraic geometry and coding theory arXiv: 1506. 02047 ( 2015 )."},{"key":"e_1_3_2_1_5_1","volume-title":"Fast Matrix Multiplication","author":"Bl\u00e4ser M.","year":"2013","unstructured":"M. Bl\u00e4ser, Fast Matrix Multiplication, Theory of Computing Library 5 ( 2013 ), 1-60."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/pdr018"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0080378"},{"key":"e_1_3_2_1_8_1","volume-title":"36th ACM Symposium on Foundations of Computer Science (FOCS 1995 ), 362-373","author":"Cai J.","unstructured":"J. Cai and D. Sivakumar, The resolution of a Hartmanis conjecture, 36th ACM Symposium on Foundations of Computer Science (FOCS 1995 ), 362-373."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1615"},{"key":"e_1_3_2_1_10_1","unstructured":"A. Cohen and G. Moshkovitz An optimal inverse theorem arXiv:2102.10509 ( 2021 )."},{"key":"e_1_3_2_1_11_1","volume-title":"The G-stable rank for tensors, arXiv","author":"Derksen H.","year":"2002","unstructured":"H. Derksen, The G-stable rank for tensors, arXiv: 2002. 08435 ( 2020 )."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1080\/03081087.2017.1337058"},{"key":"e_1_3_2_1_13_1","first-page":"345","volume":"23","author":"Dvir Z.","unstructured":"Z. Dvir, K. J\u00e1nos and S. Lovett, Variety evasive sets, Comput. Complexity 23 ( 2014 ), 345-362.","journal-title":"Comput. Complexity"},{"key":"e_1_3_2_1_14_1","first-page":"241","volume":"71","author":"Edmonds J.","unstructured":"J. Edmonds, Systems of distinct representatives and linear algebra, J. Res. Natl. Bur. Stand. 71 ( 1967 ), 241-245","journal-title":"J. Res. Natl. Bur. Stand."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1112\/S0025579309000400"},{"key":"e_1_3_2_1_16_1","unstructured":"M. Fortin and C. Reutenauer Commutative\/noncommutative rank of linear matrices and subspaces of matrices of low rank S\u00e9min. Lothar. Comb. 52 ( 2004 )."},{"key":"e_1_3_2_1_17_1","series-title":"SIAM J. Comput. 8 ( 1979 )","first-page":"431","volume-title":"A note on sparse complete sets","author":"Fortune S.","unstructured":"S. Fortune, A note on sparse complete sets, SIAM J. Comput. 8 ( 1979 ), 431-433."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-019-09417-z"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-010-0106-3"},{"key":"e_1_3_2_1_20_1","first-page":"1","volume-title":"Contrib. Discrete Math. 4 ( 2009 )","author":"Green B.","unstructured":"B. Green and T. Tao, The distribution of polynomials over finite fields, with applications to the Gowers norms, Contrib. Discrete Math. 4 ( 2009 ), 1-36."},{"key":"e_1_3_2_1_21_1","unstructured":"J. A. Grochow NP-hard sets are not sparse unless P=NP: An exposition of a simple proof of Mahaney's Theorem with applications arXiv:1610.05825 ( 2016 )."},{"key":"e_1_3_2_1_22_1","volume-title":"42nd ACM Symposium on Theory of Computing (STOC 2010 ), 331-340","author":"Haramaty E.","unstructured":"E. Haramaty and A. Shpilka, On the structure of cubic and quartic polynomials, 42nd ACM Symposium on Theory of Computing (STOC 2010 ), 331-340."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2189-8"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80004-8"},{"key":"e_1_3_2_1_25_1","first-page":"1","volume-title":"Discrete Anal. 7 ( 2020 )","author":"Janzer O.","unstructured":"O. Janzer, Polynomial bound for the partition rank vs the analytic rank of tensors, Discrete Anal. 7 ( 2020 ), 1-18."},{"key":"e_1_3_2_1_26_1","volume-title":"49th ACM Symposium on Foundations of Computer Science (FOCS 2008 ), 166-175","author":"Kaufman T.","unstructured":"T. Kaufman and S. Lovett, Worst case to average case reductions for polynomials, 49th ACM Symposium on Foundations of Computer Science (FOCS 2008 ), 166-175."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00029-017-0335-5"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-020-00542-4"},{"key":"e_1_3_2_1_29_1","first-page":"963","volume-title":"J. Am. Math. Soc. 1 ( 1988 )","author":"Kollar J.","unstructured":"J. Kollar, Sharp efective Nullstellensatz, J. Am. Math. Soc. 1 ( 1988 ), 963-975."},{"key":"e_1_3_2_1_30_1","volume-title":"35th Computational Complexity Conference (CCC 2020 ) 35","author":"Kopparty S.","unstructured":"S. Kopparty, G. Moshkovitz, and J. Zuiddam, Geometric rank of tensors and subrank of matrix multiplication, 35th Computational Complexity Conference (CCC 2020 ) 35, 1-21 (to appear in Discrete Anal.)."},{"key":"e_1_3_2_1_31_1","first-page":"1","volume-title":"Discrete Anal. 7 ( 2019 )","author":"Lovett S.","unstructured":"S. Lovett, The analytic rank of tensors and its applications, Discrete Anal. 7 ( 2019 ), 1-10."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90002-2"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-019-00505-4"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220030"},{"key":"e_1_3_2_1_35_1","volume-title":"\u201cslice rank","author":"Sawin W.","year":"2016","unstructured":"W. Sawin and T. Tao, Notes on the \u201cslice rank\u201d of tensors, https:\/\/terrytao. wordpress.com\/ 2016 \/08\/24\/notes-on-the-slice-rank-of-tensors\/ ( 2016 )."},{"key":"e_1_3_2_1_36_1","volume-title":"Basic algebraic geometry 1","author":"Shafarevich I. R.","year":"2013","unstructured":"I. R. Shafarevich, Basic algebraic geometry 1, Springer-Verlag (third edition), 2013."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392473"},{"key":"e_1_3_2_1_38_1","first-page":"184","volume":"264","author":"Strassen V.","unstructured":"V. Strassen, Vermeidung von divisionen, J. Reine Angew. Math. 264 ( 1973 ), 184-202.","journal-title":"J. Reine Angew. Math."},{"key":"e_1_3_2_1_39_1","unstructured":"T. Tao Bezout's inequality https:\/\/terrytao.wordpress.com\/ 2011 \/03\/23\/bezoutsinequality\/ ( 2011 )."},{"key":"e_1_3_2_1_40_1","unstructured":"T. Tao A symmetric formulation of the Croot-Lev-Pach-Ellenberg-Gijswijt capset bound https:\/\/terrytao.wordpress.com\/ 2016 \/05\/18\/a-symmetric-formulation-ofthe-croot-lev-pach-ellenberg-gijswijt-capset-bound ( 2016 )."},{"key":"e_1_3_2_1_41_1","first-page":"189","volume-title":"Theor. Comput. Sci. 8 ( 1979 )","author":"Valiant L.","unstructured":"L. Valiant, The complexity of computing the permanent, Theor. Comput. Sci. 8 ( 1979 ), 189-201."}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy","acronym":"STOC '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451007","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451007","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451007","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:44Z","timestamp":1750197704000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451007"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":41,"alternative-id":["10.1145\/3406325.3451007","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451007","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}