{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,6,15]],"date-time":"2022-06-15T11:08:34Z","timestamp":1655291314392},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,3,4]],"date-time":"2020-03-04T00:00:00Z","timestamp":1583280000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,3,4]],"date-time":"2020-03-04T00:00:00Z","timestamp":1583280000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2020,4]]},"DOI":"10.1007\/s00493-019-4009-0","type":"journal-article","created":{"date-parts":[[2020,3,4]],"date-time":"2020-03-04T13:02:26Z","timestamp":1583326946000},"page":"149-178","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Unbalancing Sets and An Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits"],"prefix":"10.1007","volume":"40","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[]},{"given":"Mrinal","family":"Kumar","sequence":"additional","affiliation":[]},{"given":"Ben Lee","family":"Volk","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,3,4]]},"reference":[{"key":"4009_CR1","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1109\/18.2610","volume":"34","author":"N Alon","year":"1988","unstructured":"N. Alon, E. E. Bergmann, D. Coppersmith and A. M. Odlyzko: Balancing sets of vectors, IEEE Trans. Information Theory34 (1988), 128\u2013130.","journal-title":"IEEE Trans. Information Theory"},{"key":"4009_CR2","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/s003730200003","volume":"18","author":"R P Anstee","year":"2002","unstructured":"R. P. Anstee, L. R\u00f3nyai and A. Sali: Shattering news, Graphs and Combinatorics18 (2002), 59\u201373.","journal-title":"Graphs and Combinatorics"},{"key":"4009_CR3","volume-title":"The Probabilistic Method","author":"N Alon","year":"2016","unstructured":"N. Alon and J. H. Spencer: The Probabilistic Method, Wiley Publishing, 4th edition, 2016.","edition":"4th edition"},{"key":"4009_CR4","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/0020-0190(84)90018-8","volume":"18","author":"S J Berkowitz","year":"1984","unstructured":"S. J. Berkowitz: On computing the determinant in small parallel time using a small number of processors, Information Processing Letters18 (1984), 147\u2013150.","journal-title":"Information Processing Letters"},{"key":"4009_CR5","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1112\/plms\/83.3.532","volume":"83","author":"R C Baker","year":"2001","unstructured":"R. C. Baker, G. Harman and J. Pintz: The difference between consecutive primes, ii, Proceedings of the London Mathematical Society83 (2001), 532\u2013562.","journal-title":"Proceedings of the London Mathematical Society"},{"key":"4009_CR6","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0304-3975(83)90110-X","volume":"22","author":"W Baur","year":"1983","unstructured":"W. Baur and V. Strassen: The complexity of partial derivatives, Theoretical Computer Science22 (1983), 317\u2013330.","journal-title":"Theoretical Computer Science"},{"key":"4009_CR7","volume-title":"Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2018)","author":"S Chillara","year":"2018","unstructured":"S. Chillara, C. Engels, N. Limaye and S. Srinivasan: A near-optimal depth-hierarchy theorem for small-depth multilinear circuits, in: Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2018), pages 934\u2013945. IEEE Computer Society, 2018."},{"key":"4009_CR8","volume-title":"Foundation and Trends in Theoretical Computer Science","author":"X Chen","year":"2011","unstructured":"X. Chen, N. Kayal and A. Wigderson: Partial Derivatives in Arithmetic Complexity (and beyond), Foundation and Trends in Theoretical Computer Science, 2011."},{"key":"4009_CR9","unstructured":"S. Chillara, N. Limaye and S. Srinivasan: A quadratic size-hierarchy theorem for small-depth multilinear formulas, in: Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP 2018), volume 107 of LIPIcs, 36:1-36:13. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2018."},{"key":"4009_CR10","unstructured":"S. Chillara, N. Limaye and S. Srinivasan: Small-depth multilinear formula lower bounds for iterated matrix multiplication, with applications, in: Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), volume 96 of LIPIcs, 21:1-21:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2018."},{"key":"4009_CR11","doi-asserted-by":"publisher","first-page":"618","DOI":"10.1137\/0205040","volume":"5","author":"L Csanky","year":"1976","unstructured":"L. Csanky: Fast parallel matrix inversion algorithms, SIAM J. Comput.5 (1976), 618\u2013623.","journal-title":"SIAM J. Comput."},{"key":"4009_CR12","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/BF01788526","volume":"3","author":"H Enomoto","year":"1987","unstructured":"H. Enomoto, P. Frankl, N. Ito and K. Nomura: Codes with given distances, Graphs Combin. 3 (1987), 25\u201338.","journal-title":"Graphs Combin"},{"key":"4009_CR13","first-page":"118","volume-title":"Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, 16th International Symposium, AAECC-16, Las Vegas, NV, USA, February 20\u201324, 2006, Proceedings","author":"J B Farr","year":"2006","unstructured":"J. B. Farr and S. Gao: Computing gr\u00f6bner bases for vanishing ideals of finite sets of points, in: Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, 16th International Symposium, AAECC-16, Las Vegas, NV, USA, February 20\u201324, 2006, Proceedings, 118\u2013127, 2006."},{"key":"4009_CR14","first-page":"128","volume-title":"Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC 2014)","author":"H Fournier","year":"2014","unstructured":"H. Fournier, N. Limaye, G. Malod and S. Srinivasan: Lower bounds for depth 4 formulas computing iterated matrix multiplication, in: Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC 2014), 128\u2013135, 2014."},{"key":"4009_CR15","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1090\/S0002-9947-1987-0871675-6","volume":"300","author":"P Frankl","year":"1987","unstructured":"P. Frankl and V. R\u00f6dl: Forbidden intersections, Trans. Amer. Math. Soc.300 (1987), 259\u2013286.","journal-title":"Trans. Amer. Math. Soc."},{"key":"4009_CR16","first-page":"577","volume-title":"Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC 1998)","author":"D Grigoriev","year":"1998","unstructured":"D. Grigoriev and M. Karpinski: An exponential lower bound for depth 3 arithmetic circuits, in: Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC 1998), 577\u2013582, 1998."},{"issue":"6","key":"4009_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2629541","volume":"61","author":"Ankit Gupta","year":"2014","unstructured":"A. Gupta, P. Kamath, N. Kayal and R. Saptharishi: Approaching the chasm at depth four, Journal of the ACM61 (2014), 33:1-33:16.","journal-title":"Journal of the ACM"},{"key":"4009_CR18","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/s002009900021","volume":"10","author":"D Grigoriev","year":"2000","unstructured":"D. Grigoriev and A. A. Razborov: Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields, Appl. Algebra Eng. Commun. Comput.10 (2000), 465\u2013487","journal-title":"Appl. Algebra Eng. Commun. Comput."},{"key":"4009_CR19","first-page":"333","volume":"47","author":"G Heged\u0171s","year":"2010","unstructured":"G. Heged\u0171s: Balancing sets of vectors, Studia Sci. Math. Hungar.47 (2010), 333\u2013349.","journal-title":"Studia Sci. Math. Hungar."},{"key":"4009_CR20","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1023\/A:1022934815185","volume":"17","author":"G Heged\u0171s","year":"2003","unstructured":"G. Heged\u0171s and L. R\u00f3nyai: Gr\u00f6bner bases for complete uniform families, J. Algebraic Combin.17 (2003), 171\u2013180.","journal-title":"J. Algebraic Combin."},{"key":"4009_CR21","volume-title":"Proceedings of the 33rd Internationl Symposium on the Mathematical Foundations of Computer Science (MFCS 2008)","author":"M J Jansen","year":"2008","unstructured":"M. J. Jansen: Lower bounds for syntactically multilinear algebraic branching programs, in: Proceedings of the 33rd Internationl Symposium on the Mathematical Foundations of Computer Science (MFCS 2008), volume 5162 of Lecture Notes in Computer Science, pages 407\u2013418. Springer, 2008."},{"key":"4009_CR22","doi-asserted-by":"publisher","first-page":"678","DOI":"10.1137\/0214050","volume":"14","author":"K Kalorkoti","year":"1985","unstructured":"K. Kalorkoti: A Lower Bound for the Formula Size of Rational Functions, SIAM J. Comput.14 (1985), 678\u2013687.","journal-title":"SIAM J. Comput."},{"key":"4009_CR23","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1109\/FOCS.2014.15","volume-title":"Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2014)","author":"N Kayal","year":"2014","unstructured":"N. Kayal, N. Limaye, C. Saha and S. Srinivasan: An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Circuits, in: Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2014), 61\u201370, 2014."},{"key":"4009_CR24","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1109\/TIT.1986.1057136","volume":"32","author":"D E Knuth","year":"1986","unstructured":"D. E. Knuth: Efficient balanced codes, IEEE Trans. Information Theory32 (1986), 51\u201353.","journal-title":"IEEE Trans. Information Theory"},{"key":"4009_CR25","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1109\/FOCS.2014.46","volume-title":"Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2014)","author":"M Kumar","year":"2014","unstructured":"M. Kumar and S. Saraf: On the power of homogeneous depth 4 arithmetic circuits, in: Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2014), 364\u2013373, 2014."},{"key":"4009_CR26","unstructured":"M. Kumar and R. Saptharishi: An exponential lower bound for homogeneous depth-5 circuits over finite fields, in: Proceedings of the 32nd Annual Computational Complexity Conference (CCC 2017), volume 79, 31:1-31:30, 2017."},{"key":"4009_CR27","unstructured":"M. Kumar: A quadratic lower bound for homogeneous algebraic branching programs, in: Proceedings of the 32nd Annual Computational Complexity Conference (CCC 2017), volume 79, 19:1-19:16, 2017."},{"key":"4009_CR28","volume-title":"Chicago J. Theor. Comput. Sci.","author":"M Mahajan","year":"1997","unstructured":"M. Mahajan and V. Vinay: Determinant: Combinatorics, algorithms, and complexity, Chicago J. Theor. Comput. Sci., 1997."},{"key":"4009_CR29","first-page":"410","volume-title":"Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (STOC 1991)","author":"N Nisan","year":"1991","unstructured":"N. Nisan: Lower bounds for non-commutative computation, in: Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (STOC 1991), 410\u2013418, 1991."},{"key":"4009_CR30","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF01294256","volume":"6","author":"N Nisan","year":"1997","unstructured":"N. Nisan and A. Wigderson: Lower bounds on arithmetic circuits via partial derivatives, Computational Complexity6 (1997), 217\u2013234","journal-title":"Computational Complexity"},{"key":"4009_CR31","doi-asserted-by":"publisher","first-page":"121","DOI":"10.4086\/toc.2006.v002a006","volume":"2","author":"R Raz","year":"2006","unstructured":"R. Raz: Separation of multilinear circuit and formula size, Theory of Computing2 (2006), 121\u2013135","journal-title":"Theory of Computing"},{"key":"4009_CR32","doi-asserted-by":"crossref","unstructured":"R. Raz: Multi-linear formulas for permanent and determinant are of super-polynomial size, J. ACM56 (2009), 8:1-8:17.","DOI":"10.1145\/1502793.1502797"},{"key":"4009_CR33","doi-asserted-by":"publisher","first-page":"135","DOI":"10.4086\/toc.2010.v006a007","volume":"6","author":"R Raz","year":"2010","unstructured":"R. Raz: Elusive functions and lower bounds for arithmetic circuits, Theory of Computing6 (2010), 135\u2013177.","journal-title":"Theory of Computing"},{"key":"4009_CR34","doi-asserted-by":"publisher","first-page":"1624","DOI":"10.1137\/070707932","volume":"38","author":"R Raz","year":"2008","unstructured":"R. Raz, A. Shpilka and A. Yehudayoff: A lower bound for the size of syntactically multilinear arithmetic circuits, SIAM J. Comput.38 (2008), 1624\u20131647","journal-title":"SIAM J. Comput."},{"key":"4009_CR35","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/s00037-008-0254-0","volume":"17","author":"R Raz","year":"2008","unstructured":"R. Raz and A. Yehudayoff: Balancing syntactically multilinear arithmetic circuits, Computational Complexity17 (2008), 515\u2013535.","journal-title":"Computational Complexity"},{"key":"4009_CR36","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/s00037-009-0270-8","volume":"18","author":"R Raz","year":"2009","unstructured":"R. Raz and A. Yehudayoff: Lower bounds and separations for constant depth multilinear circuits, Computational Complexity18 (2009), 171\u2013207","journal-title":"Computational Complexity"},{"key":"4009_CR37","volume-title":"Github survey","author":"R Saptharishi","year":"2016","unstructured":"R. Saptharishi: A survey of lower bounds in arithmetic circuit complexity, Github survey, https:\/\/github.com\/dasarpmar\/lowerbounds-survey\/, 2016."},{"key":"4009_CR38","volume-title":"Hypergeometric tail inequalities: ending the insanity, arXiv preprint","author":"M Skala","year":"2013","unstructured":"M. Skala: Hypergeometric tail inequalities: ending the insanity, arXiv preprint arXiv:1311.5939, 2013."},{"key":"4009_CR39","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/BF01436566","volume":"20","author":"V Strassen","year":"1973","unstructured":"V. Strassen: Die berechnungskomplexit\u00e4t von elementarsymmetrischen funktionen und von interpolationskoeffizienten, Numerische Mathematik20 (1973), 238\u2013251.","journal-title":"Numerische Mathematik"},{"key":"4009_CR40","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1561\/0400000039","volume":"5","author":"A Shpilka","year":"2010","unstructured":"A. Shpilka and A. Yehudayoff: Arithmetic circuits: A survey of recent results and open questions, Foundations and Trends in Theoretical Computer Science5 (2010), 207\u2013388.","journal-title":"Foundations and Trends in Theoretical Computer Science"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-019-4009-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-019-4009-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-019-4009-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,4]],"date-time":"2021-03-04T00:49:34Z","timestamp":1614818974000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-019-4009-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,4]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["4009"],"URL":"http:\/\/dx.doi.org\/10.1007\/s00493-019-4009-0","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":["Computational Mathematics","Discrete Mathematics and Combinatorics"],"published":{"date-parts":[[2020,3,4]]},"assertion":[{"value":"10 June 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 March 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 March 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}