{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,2]],"date-time":"2024-07-02T16:10:21Z","timestamp":1719936621459},"reference-count":56,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,4,16]],"date-time":"2024-04-16T00:00:00Z","timestamp":1713225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,4,16]],"date-time":"2024-04-16T00:00:00Z","timestamp":1713225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2024,6]]},"abstract":"Abstract<\/jats:title>For a polynomial f<\/jats:italic>,\na weighted sum-of-squares representation (SOS)<\/jats:italic> has the form \n$$f = \\sum_{i\\in [s]} c_i f_i^2$$<\/jats:tex-math>\n \n f<\/mml:mi>\n =<\/mml:mo>\n \n \u2211<\/mml:mo>\n \n i<\/mml:mi>\n \u2208<\/mml:mo>\n [<\/mml:mo>\n s<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msub>\n \n c<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n \n f<\/mml:mi>\n i<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msubsup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where the weights<\/jats:italic>$$c_i$$<\/jats:tex-math>\n \n c<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> are field elements. \nThe size of the representation is the number of monomials that appear across the $$f_i$$<\/jats:tex-math>\n \n f<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>'s.\nIts minimum across all such decompositions is called the support-sum S(f)<\/jats:italic> of f<\/jats:italic>.<\/jats:p>For a univariate polynomial f<\/jats:italic> of degree d<\/jats:italic> of full support,\na lower bound for the support-sum is $$S(f) \\ge \\sqrt d$$<\/jats:tex-math>\n \n S<\/mml:mi>\n \n (<\/mml:mo>\n f<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2265<\/mml:mo>\n \n d<\/mml:mi>\n <\/mml:msqrt>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.\nWe show that the existence of an explicit univariate polynomial f<\/jats:italic>\nwith support-sum just slightly larger than the lower bound, that is, $$S(f) \\ge d^{0.5+\\varepsilon}$$<\/jats:tex-math>\n \n S<\/mml:mi>\n \n (<\/mml:mo>\n f<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2265<\/mml:mo>\n \n d<\/mml:mi>\n \n 0.5<\/mml:mn>\n +<\/mml:mo>\n \u03b5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, \nfor some $$\\varepsilon > 0$$<\/jats:tex-math>\n \n \u03b5<\/mml:mi>\n ><\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>,\nimplies that $$\\ne$$<\/jats:tex-math>\n \u2260<\/mml:mo>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>,\nthe<\/jats:italic> major open problem in algebraic complexity.\nIn fact, our proof works for some subconstant functions $$\\varepsilon(d) > 0$$<\/jats:tex-math>\n \n \u03b5<\/mml:mi>\n (<\/mml:mo>\n d<\/mml:mi>\n )<\/mml:mo>\n ><\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> as well.\nWe also consider the sum-of-cubes representation (SOC)<\/jats:italic> of polynomials. We show that an explicit hard polynomial\nimplies both blackbox-PIT is in , and $$\\neq$$<\/jats:tex-math>\n \u2260<\/mml:mo>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s00037-024-00249-0","type":"journal-article","created":{"date-parts":[[2024,4,16]],"date-time":"2024-04-16T07:01:56Z","timestamp":1713250916000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Weighted Sum-of-Squares Lower Bounds for Univariate Polynomials Imply $$\\text{VP} \\neq \\text{VNP}$$"],"prefix":"10.1007","volume":"33","author":[{"given":"Pranjal","family":"Dutta","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nitin","family":"Saxena","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Thierauf","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,4,16]]},"reference":[{"key":"249_CR1","unstructured":"Manindra Agrawal (2020). Private Communication."},{"key":"249_CR2","doi-asserted-by":"crossref","unstructured":"Manindra Agrawal, Sumanta Ghosh & Nitin Saxena (2019). Bootstrapping variables in algebraic circuits. Proceedings of the National Academy of Sciences 116(17), 8107\u20138118. Earlier in Symposium on Theory of Computing, 2018 (STOC\u201918).","DOI":"10.1073\/pnas.1901272116"},{"key":"249_CR3","doi-asserted-by":"crossref","unstructured":"Manindra Agrawal & V Vinay (2008). Arithmetic Circuits: A Chasm at Depth Four. In Foundations of Computer Science, 2008. FOCS\u201908. IEEE 49th Annual IEEE Symposium on, 67\u201375. IEEE.","DOI":"10.1109\/FOCS.2008.32"},{"key":"249_CR4","unstructured":"Boaz Barak & Ankur Moitra (2016). Noisy tensor completion via the Sum-of-squares Hierarchy. In Conference on Learning Theory, 417\u2013445"},{"key":"249_CR5","doi-asserted-by":"crossref","unstructured":"Peter B\u00fcrgisser (2001). The complexity of factors of multivariate polynomials. In In Proc. 42th IEEE Symp. on Foundations of Comp. Science","DOI":"10.1109\/SFCS.2001.959912"},{"key":"249_CR6","doi-asserted-by":"crossref","unstructured":"Peter B\u00fcrgisser (2004). The complexity of factors of multivariate polynomials. Foundations of Computational Mathematics 4(4), 369\u2013396. (Preliminary version in FOCS 2001).","DOI":"10.1007\/s10208-002-0059-5"},{"key":"249_CR7","unstructured":"Peter B\u00fcrgisser (2013). Completeness and Reduction in Algebraic Complexity Theory, volume 7. Springer Science & Business Media."},{"key":"249_CR8","unstructured":"Peter B\u00fcrgisser , Michael Clausen & Amin Shokrollahi (2013). Algebraic Complexity Theory, volume 315. Springer Science & Business Media."},{"key":"249_CR9","doi-asserted-by":"crossref","unstructured":"Xi Chen, Neeraj Kayal & Avi Wigderson (2011). Partial derivatives in arithmetic complexity and beyond. Now Publishers Inc.","DOI":"10.1561\/9781601984814"},{"key":"249_CR10","doi-asserted-by":"crossref","unstructured":"Richard A. Demillo & Richard J. Lipton (1978). A probabilistic remark on algebraic program testing. Information Processing Letters 7(4), 193 \u2013 195. ISSN 0020-0190.","DOI":"10.1016\/0020-0190(78)90067-4"},{"key":"249_CR11","doi-asserted-by":"crossref","unstructured":"Pranjal Dutta (2021). Real $$\\tau$$-Conjecture for Sum-of-Squares: A Unified Approach to Lower Bound and Derandomization. In International Computer Science Symposium in Russia, 78\u2013101. Springer.","DOI":"10.1007\/978-3-030-79416-3_5"},{"key":"249_CR12","unstructured":"Pranjal Dutta (2022). A tale of hardness, de-randomization and de-bordering in complexity theory. Ph.D. thesis, Chennai Mathematical Institute."},{"key":"249_CR13","doi-asserted-by":"crossref","unstructured":"Michael A Forbes & Amir Shpilka (2018). A PSPACE construction of a hitting set for the closure of small algebraic circuits. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 1180\u20131192.","DOI":"10.1145\/3188745.3188792"},{"key":"249_CR14","doi-asserted-by":"crossref","unstructured":"Ignacio Garcia-Marco & Pascal Koiran (2017). Lower bounds by Birkhoff interpolation. Journal of Complexity 39, 38\u201350.","DOI":"10.1016\/j.jco.2016.10.001"},{"key":"249_CR15","unstructured":"Joshua A. Grochow, Ketan D. Mulmuley & Youming Qiao (2016). Boundaries of VP and VNP. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55, 34:1\u201334:14."},{"key":"249_CR16","doi-asserted-by":"publisher","unstructured":"Zeyu Guo, Mrinal Kumar, Ramprasad Saptharishi & Noam Solomon (2019a). Derandomization from Algebraic Hardness: Treading the Borders. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, 147\u2013157. URL https:\/\/doi.org\/10.1109\/FOCS.2019.00018. Online version: https:\/\/mrinalkr.bitbucket.io\/papers\/newprg.pdf","DOI":"10.1109\/FOCS.2019.00018"},{"key":"249_CR17","doi-asserted-by":"crossref","unstructured":"Zeyu Guo, Nitin Saxena & Amit Sinhababu (2019b). Algebraic Dependencies and PSPACE Algorithms in Approximative Complexity over Any Field. Theory of Computing 15(1), 1\u201330.","DOI":"10.4086\/toc.2019.v015a016"},{"key":"249_CR18","doi-asserted-by":"crossref","unstructured":"Ankit Gupta, Pritish Kamath, Neeraj Kayal & Ramprasad Saptharishi (2013). Arithmetic circuits: A chasm at depth three. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 578\u2013587. IEEE.","DOI":"10.1109\/FOCS.2013.68"},{"key":"249_CR19","doi-asserted-by":"crossref","unstructured":"Joos Heintz & Claus-Peter Schnorr (1980). Testing polynomials which are easy to compute. In Proceedings of the twelfth annual ACM symposium on Theory of computing, 262\u2013272. ACM.","DOI":"10.1145\/800141.804674"},{"key":"249_CR20","doi-asserted-by":"crossref","unstructured":"Joos Heintz & Malte Sieveking (1980). Lower bounds for polynomials with algebraic coefficients. Theoretical Computer Science 11(3), 321\u2013330.","DOI":"10.1016\/0304-3975(80)90019-5"},{"key":"249_CR21","doi-asserted-by":"crossref","unstructured":"Pavel Hrube\u0161, Avi Wigderson & Amir Yehudayoff (2011). Non\u2013commutative circuits and the sum-of-squares problem. Journal of the American Mathematical Society 24(3), 871\u2013898.","DOI":"10.1090\/S0894-0347-2011-00694-2"},{"key":"249_CR22","doi-asserted-by":"crossref","unstructured":"Christian Ikenmeyer & JM Landsberg (2017). On the complexity of the permanent in various computational models. Journal of Pure and Applied Algebra 221(12), 2911\u20132927.","DOI":"10.1016\/j.jpaa.2017.02.008"},{"key":"249_CR23","doi-asserted-by":"crossref","unstructured":"Valentine Kabanets & Russell Impagliazzo (2004). Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity 13(1-2), 1\u201346","DOI":"10.1007\/s00037-004-0182-6"},{"key":"249_CR24","doi-asserted-by":"crossref","unstructured":"Neeraj Kayal, Pascal Koiran, Timoth\u00e9e Pecatte & Chandan Saha (2015). Lower bounds for sums of powers of low degree univariates. In International Colloquium on Automata, Languages, and Programming, 810\u2013821. Springer.","DOI":"10.1007\/978-3-662-47672-7_66"},{"key":"249_CR25","unstructured":"Pascal Koiran (2011). Shallow circuits with high-powered inputs. In Innovations in Computer Science - ICS 2010, Tsinghua University, Beijing, China, January 7-9, 2011. Proceedings, 309\u2013320. URL http:\/\/conference.iiis.tsinghua.edu.cn\/ICS2011\/content\/papers\/5.html."},{"key":"249_CR26","doi-asserted-by":"crossref","unstructured":"Pascal Koiran (2012). Arithmetic circuits: The chasm at depth four gets wider. Theoretical Computer Science 448, 56\u201365.","DOI":"10.1016\/j.tcs.2012.03.041"},{"key":"249_CR27","doi-asserted-by":"crossref","unstructured":"Pascal Koiran, Timoth\u00e9e Pecatte & Ignacio Garcia-Marco (2018). On the linear independence of shifted powers. Journal of Complexity 45, 67\u201382.","DOI":"10.1016\/j.jco.2017.11.002"},{"key":"249_CR28","doi-asserted-by":"crossref","unstructured":"Pascal Koiran & Sylvain Perifel (2011). Interpolation in Valiants theory. Computational Complexity 20(1), 1\u201320.","DOI":"10.1007\/s00037-011-0002-8"},{"key":"249_CR29","doi-asserted-by":"crossref","unstructured":"Leopold Kronecker (1882). Grundz\u00fcge einer arithmetischen Theo rie der algebraischen Gr\u00f6ssen.(Abdruck einer Festschrift zu Herrn EE Kummers Doctor-Jubil\u00e4um, 10. September 1881.). Journal f\u00fcr die reine und angewandte Mathematik 92, 1\u2013122.","DOI":"10.1515\/9783112342404-001"},{"key":"249_CR30","doi-asserted-by":"crossref","unstructured":"Mrinal Kumar (2019). A quadratic lower bound for homogeneous algebraic branching programs. computational complexity 28(3), 409\u2013435.","DOI":"10.1007\/s00037-019-00186-3"},{"key":"249_CR31","unstructured":"Mrinal Kumar, Ramprasad Saptharishi & Noam Solomon (2019a). Derandomization from Algebraic Hardness: Treading the Borders. https:\/\/arxiv.org\/pdf\/1905.00091v1.pdf."},{"key":"249_CR32","doi-asserted-by":"crossref","unstructured":"Mrinal Kumar, Ramprasad Saptharishi & Anamay Tengse (2019b). Near-optimal Bootstrapping of Hitting Sets for Algebraic Circuits. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 639\u2013646.","DOI":"10.1137\/1.9781611975482.40"},{"key":"249_CR33","doi-asserted-by":"crossref","unstructured":"Jean B Lasserre (2007). A sum of squares approximation of nonnegative polynomials. SIAM review 49(4), 651\u2013669.","DOI":"10.1137\/070693709"},{"key":"249_CR34","doi-asserted-by":"crossref","unstructured":"Monique Laurent (2009). Sums of squares, moment matrices and optimization over polynomials. In Emerging applications of algebraic geometry, 157\u2013270. Springer.","DOI":"10.1007\/978-0-387-09686-5_7"},{"key":"249_CR35","doi-asserted-by":"crossref","unstructured":"Thomas Lehmkuhl & Thomas Lickteig (1989). On the order of approximation in approximative triadic decompositions of tensors. Theoretical computer science 66(1), 1\u201314.","DOI":"10.1016\/0304-3975(89)90141-2"},{"key":"249_CR36","doi-asserted-by":"crossref","unstructured":"Meena Mahajan (2014). Algebraic Complexity Classes. In Perspectives in Computational Complexity, 51\u201375. Springer.","DOI":"10.1007\/978-3-319-05446-9_4"},{"key":"249_CR37","doi-asserted-by":"crossref","unstructured":"Meena Mahajan & V Vinay (1999). Determinant: Old algorithms, new insights. SIAM Journal on Discrete Mathematics 12(4), 474\u2013490.","DOI":"10.1137\/S0895480198338827"},{"key":"249_CR38","doi-asserted-by":"crossref","unstructured":"John C Mason & David C Handscomb (2002). Chebyshevpolynomials. CRC press.","DOI":"10.1201\/9781420036114"},{"key":"249_CR39","doi-asserted-by":"crossref","unstructured":"Ketan Mulmuley (2017). Geometric complexity theory V: Efficient algorithms for Noether normalization. Journal of the American Mathematical Society 30(1), 225\u2013309.","DOI":"10.1090\/jams\/864"},{"key":"249_CR40","doi-asserted-by":"crossref","unstructured":"Ketan D Mulmuley & Milind Sohoni (2001). Geometric complexity theory I: An approach to the P vs. NP and related problems. SIAM Journal on Computing 31(2), 496\u2013526.","DOI":"10.1137\/S009753970038715X"},{"key":"249_CR41","doi-asserted-by":"crossref","unstructured":"Ketan D Mulmuley & Milind Sohoni (2008). Geometric complexity theory II: Towards explicit obstructions for embeddings among class varieties. SIAM Journal on Computing 38(3), 1175\u20131206.","DOI":"10.1137\/080718115"},{"key":"249_CR42","doi-asserted-by":"crossref","unstructured":"Noam Nisan & Avi Wigderson (1994). Hardness vs randomness. Journal of computer and System Sciences 49(2), 149\u2013167.","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"249_CR43","unstructured":"Oystein Ore (1922). \u00dcber h\u00f6here Kongruenzen. Norsk Mat. Forenings Skrifter 1(7), 15."},{"key":"249_CR44","doi-asserted-by":"crossref","unstructured":"Ran Raz (2010). Elusive Functions and Lower Bounds for Arithmetic Circuits. Theory Comput. 6(1), 135\u2013177. URL https:\/\/doi.org\/10.4086\/toc.2010.v006a007.","DOI":"10.4086\/toc.2010.v006a007"},{"key":"249_CR45","doi-asserted-by":"crossref","unstructured":"Bruce Reznick (1978). Extremal PSD forms with few terms. Duke mathematical journal 45(2), 363\u2013374.","DOI":"10.1215\/S0012-7094-78-04519-2"},{"key":"249_CR46","unstructured":"Ramprasad Saptharishi (2019). A survey of lower bounds in arithmetic circuit complexity. Github survey."},{"key":"249_CR47","unstructured":"Nitin Saurabh (2012). ALGEBRAIC MODELS OF COMPUTATION. MS Thesis"},{"key":"249_CR48","doi-asserted-by":"crossref","unstructured":"J. T. Schwartz (1980). Fast Probabilistic Algorithms for Verification of Polynomial Identities. J. ACM 27(4), 701\u2013717. ISSN 0004-5411.","DOI":"10.1145\/322217.322225"},{"key":"249_CR49","doi-asserted-by":"crossref","unstructured":"Amir Shpilka & Amir Yehudayoff (2010). Arithmetic Circuits: A survey of recent results and open questions. Foundations and Trends\u00ae in Theoretical Computer Science 5(3\u20134), 207\u2013388","DOI":"10.1561\/0400000039"},{"key":"249_CR50","doi-asserted-by":"crossref","unstructured":"Michael Shub & Steve Smale (1995). On the intractability of Hilberts Nullstellensatz and an algebraic version of NP$$\\neq$$ P?. Duke Mathematical Journal 81(1), 47\u201354.","DOI":"10.1215\/S0012-7094-95-08105-8"},{"key":"249_CR51","doi-asserted-by":"crossref","unstructured":"Steve Smale (1998). Mathematical problems for the next century. The mathematical intelligencer 20(2), 7\u201315.","DOI":"10.1007\/BF03025291"},{"key":"249_CR52","doi-asserted-by":"crossref","unstructured":"Volker Strassen (1974). Polynomials with rational coefficients which are hard to compute. SIAM Journal on Computing 3(2), 128\u2013149.","DOI":"10.1137\/0203010"},{"key":"249_CR53","doi-asserted-by":"crossref","unstructured":"S\u00e9bastien Tavenas (2015). Improved bounds for reduction to depth 4 and depth 3. Information and Computation 240, 2\u201311","DOI":"10.1016\/j.ic.2014.09.004"},{"key":"249_CR54","doi-asserted-by":"crossref","unstructured":"Leslie G Valiant (1979). Completeness classes in algebra. In Proceedings of the 11th Annual ACM symposium on Theory of computing, 249\u2013261. ACM.","DOI":"10.1145\/800135.804419"},{"key":"249_CR55","doi-asserted-by":"publisher","unstructured":"Leslie G. Valiant, Sven Skyum, S. Berkowitz & Charles Rackoff (1983). Fast Parallel Computation of Polynomials Using Few Processors. SIAM Journal of Computing 12(4), 641\u2013644. URL https:\/\/doi.org\/10.1137\/0212043.","DOI":"10.1137\/0212043"},{"key":"249_CR56","doi-asserted-by":"crossref","unstructured":"Richard Zippel (1979). Probabilistic Algorithms for Sparse Polynomials. In Proceedings of the International Symposium on Symbolic and Algebraic Computation, EUROSAM \u201979, 216\u2013226. ISBN 3-540-09519-5.","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-024-00249-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-024-00249-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-024-00249-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,2]],"date-time":"2024-07-02T15:40:04Z","timestamp":1719934804000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-024-00249-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,16]]},"references-count":56,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["249"],"URL":"https:\/\/doi.org\/10.1007\/s00037-024-00249-0","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,16]]},"assertion":[{"value":"16 April 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"3"}}