{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:44:51Z","timestamp":1740109491674,"version":"3.37.3"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,11,12]],"date-time":"2023-11-12T00:00:00Z","timestamp":1699747200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,11,12]],"date-time":"2023-11-12T00:00:00Z","timestamp":1699747200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100014374","name":"Universitat Polit\u00e8cnica de Catalunya","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100014374","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2023,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We introduce a novel take on sum-of-squares that is able\nto reason with complex numbers and still make use of polynomial inequalities.\nThis proof system might be of independent interest since it\nallows to represent multivalued domains both with Boolean and Fourier\nencoding. We show degree and size lower bounds in this system for a\nnatural generalization of knapsack: the vanishing sums of roots of unity.\nThese lower bounds naturally apply to polynomial calculus as-well.<\/jats:p>","DOI":"10.1007\/s00037-023-00242-z","type":"journal-article","created":{"date-parts":[[2023,11,12]],"date-time":"2023-11-12T20:01:29Z","timestamp":1699819289000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On vanishing sums of roots of unity in polynomial calculus and sum-of-squares"],"prefix":"10.1007","volume":"32","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5697-8070","authenticated-orcid":false,"given":"Ilario","family":"Bonacina","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8522-362X","authenticated-orcid":false,"given":"Nicola","family":"Galesi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4003-3168","authenticated-orcid":false,"given":"Massimo","family":"Lauria","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,11,12]]},"reference":[{"key":"242_CR1","doi-asserted-by":"crossref","unstructured":"Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch &\nIddo Tzameret (2020). Semi-Algebraic Proofs, IPS Lower Bounds,\nand the \u03c4 -Conjecture: Can a Natural Number Be Negative? In Proceedings\nof the 52nd Annual ACM SIGACT Symposium on Theory of\nComputing (STOC\u201920), 54\u201367.","DOI":"10.1145\/3357713.3384245"},{"key":"242_CR2","unstructured":"Albert Atserias & Tuomas Hakoniemi (2019). Size-Degree Trade-\nOffs for Sums-of-Squares and Positivstellensatz Proofs. In Proceedings\nof the 34th Computational Complexity Conference (CCC\u201919), volume\n137 of LIPIcs, 24:1\u201324:20."},{"key":"242_CR3","doi-asserted-by":"crossref","unstructured":"Albert Atserias & Joanna Ochremiak (2018). Proof Complexity\nMeets Algebra. ACM Trans. Comput. Logic 20(1).","DOI":"10.1145\/3265985"},{"key":"242_CR4","unstructured":"Roberto J Bayardo Jr & Robert Schrag (1997). Using CSP\nlook-back techniques to solve real-world SAT instances. In Proceedings\nof the 14th National Conference on Artificial Intelligence and\n9th Conference on Innovative Applications of Artificial Intelligence \n(AAAI\u201997\/IAAI\u201997), 203\u2013208."},{"key":"242_CR5","unstructured":"Christoph Berkholz (2018). The Relation between Polynomial\nCalculus, Sherali-Adams, and Sum-of-Squares Proofs. In  Proceedings\nof the 35th Symposium on Theoretical Aspects of Computer Science\n(STACS\u201918), volume 96, 11:1\u201311:14."},{"key":"242_CR6","doi-asserted-by":"crossref","unstructured":"Grigoriy Blekherman, Jo\u00e3o Gouveia & James Pfeiffer (2016).\nSums of squares on the hypercube. Mathematische Zeitschrift 1\u201314.","DOI":"10.1007\/s00209-016-1644-7"},{"key":"242_CR7","doi-asserted-by":"crossref","unstructured":"Grigoriy Blekherman & Cordian Riener (2020). Symmetric Non-\nNegative Forms and Sums of Squares. Discrete and Computational Geometry\n65(3), 764\u2013799.","DOI":"10.1007\/s00454-020-00208-w"},{"key":"242_CR8","unstructured":"Ilario Bonacina, Nicola Galesi & Massimo Lauria (2022). On\nVanishing Sums of Roots of Unity in Polynomial Calculus and Sum-\nOf-Squares. In Proceedings of the 47th International Symposium on\nMathematical Foundations of Computer Science (MFCS\u201922), volume\n241 of LIPIcs, 23:1\u201323:15."},{"key":"242_CR9","doi-asserted-by":"crossref","unstructured":"Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo & Toniann\nPitassi (2001). Linear Gaps between Degrees for the Polynomial\nCalculus Modulo Distinct Primes. J. Comput. Syst. Sci. 62(2), 267\u2013289.\nhttps:\/\/doi.org\/10.1006\/jcss.2000.1726.","DOI":"10.1006\/jcss.2000.1726"},{"key":"242_CR10","doi-asserted-by":"crossref","unstructured":"Matthew Clegg, Jeff Edmonds & Russell Impagliazzo (1996).\nUsing the Gr\u00f6bner Basis Algorithm to Find Proofs of Unsatisfiability.\nIn Proceedings of the 28th Annual ACM Symposium on the Theory of\nComputing (STOC\u201996), 174\u2013183.","DOI":"10.1145\/237814.237860"},{"key":"242_CR11","doi-asserted-by":"crossref","unstructured":"John Conway & A. Jones (1976). Trigonometric diophantine equations\n(On vanishing sums of roots of unity). Acta Arithmetica 30(3),\n229\u2013240.","DOI":"10.4064\/aa-30-3-229-240"},{"key":"242_CR12","unstructured":"David Cox, John Little & Donal O\u2019Shea (2007). Ideals, Varieties,\nand Algorithms : An Introduction to Computational Algebraic Geometry\nand Commutative Algebra, 3rd edition . Springer."},{"key":"242_CR13","doi-asserted-by":"crossref","unstructured":"Jes\u00fas A De Loera, J. Lee, S. Margulies & S. Onn (2009). Expressing\nCombinatorial Problems by Systems of Polynomial Equations\nand Hilbert\u2019s Nullstellensatz. Comb. Probab. Comput. 18(4), 551\u2013582.","DOI":"10.1017\/S0963548309009894"},{"key":"242_CR14","doi-asserted-by":"crossref","unstructured":"Jes\u00fas A De Loera, Jon Lee, Peter N Malkin & Susan Margulies\n(2011). Computing infeasibility certificates for combinatorial\nproblems through Hilbert\u2019s Nullstellensatz. Journal of Symbolic Computation\n46(11), 1260\u20131283.","DOI":"10.1016\/j.jsc.2011.08.007"},{"key":"242_CR15","doi-asserted-by":"crossref","unstructured":"Jes\u00fas A De Loera, Susan Margulies, Michael Pernpeintner,\nEric Riedl, David Rolnick, Gwen Spencer, Despina Stasi &\nJon Swenson (2015). Graph-coloring ideals: Nullstellensatz certificates,\nGr\u00f6bner bases for chordal graphs, and hardness of Gr\u00f6bner bases.\nIn Proceedings of the 2015 ACM on International Symposium on Symbolic\nand Algebraic Computation (ISSAC\u201915), 133\u2013140.","DOI":"10.1145\/2755996.2756639"},{"key":"242_CR16","doi-asserted-by":"crossref","unstructured":"R. Dvornicich & U. Zannier (2002). Sums of roots of unity vanishing\nmodulo a prime. Archiv der Mathematik 79(2), 104\u2013108.","DOI":"10.1007\/s00013-002-8291-4"},{"key":"242_CR17","doi-asserted-by":"crossref","unstructured":"Roberto Dvornicich & Umberto Zannier (2000). On Sums of\nRoots of Unity. Monatshefte f\u00fcr Mathematik 129(2), 97\u2013108.","DOI":"10.1007\/s006050050009"},{"key":"242_CR18","doi-asserted-by":"crossref","unstructured":"Michael A. Forbes, Amir Shpilka, Iddo Tzameret & Avi\nWigderson (2021). Proof Complexity Lower Bounds from Algebraic\nCircuit Complexity. Theory Comput. 17, 1\u201388.","DOI":"10.4086\/toc.2021.v017a010"},{"key":"242_CR19","doi-asserted-by":"crossref","unstructured":"Nicola Galesi & Massimo Lauria (2010). Optimality of size-degree\ntradeoffs for polynomial calculus. ACM Trans. Comput. Log. 12(1),\n4:1\u20134:22.","DOI":"10.1145\/1838552.1838556"},{"key":"242_CR20","doi-asserted-by":"crossref","unstructured":"D. Grigoriev (2001). Complexity of Positivstellensatz proofs for the\nknapsack. Computational Complexity 10(2), 139\u2013154.","DOI":"10.1007\/s00037-001-8192-0"},{"key":"242_CR21","doi-asserted-by":"crossref","unstructured":"Dima Grigoriev (1998). Tseitin\u2019s Tautologies and Lower Bounds for\nNullstellensatz Proofs. In Proceedings of the 39th Annual Symposium\non Foundations of Computer Science (FOCS\u201998), 648\u2013652.","DOI":"10.1109\/SFCS.1998.743515"},{"key":"242_CR22","doi-asserted-by":"crossref","unstructured":"Dima Grigoriev & Edward A. Hirsch (2003). Algebraic proof systems\nover formulas. Theoretical Computer Science 303(1), 83 \u2013 102.","DOI":"10.1016\/S0304-3975(02)00446-2"},{"key":"242_CR23","doi-asserted-by":"crossref","unstructured":"Joshua A. Grochow & Toniann Pitassi (2018). Circuit Complexity,\nProof Complexity, and Polynomial Identity Testing: The Ideal Proof\nSystem. J. ACM 65(6), 37:1\u201337:59.","DOI":"10.1145\/3230742"},{"key":"242_CR24","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, P. Pudl\u00e1k & J. Sgall (1999). Lower bounds for the\npolynomial calculus and the Gr\u00f6bner basis algorithm. Computational\nComplexity 8(2), 127\u2013144.","DOI":"10.1007\/s000370050024"},{"key":"242_CR25","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo, Sasank Mouli & Toniann Pitassi (2020).\nThe Surprising Power of Constant Depth Algebraic Proofs. In  Proceedings\nof the 35th Annual ACM\/IEEE Symposium on Logic in Computer\nScience (LICS\u201920), 591\u2013603.","DOI":"10.1145\/3373718.3394754"},{"key":"242_CR26","unstructured":"Russell Impagliazzo, Sasank Mouli & Toniann Pitassi (2022).\nLower bounds for Polynomial Calculus with extension variables over\nfinite fields. Electron. Colloquium Comput. Complex. TR22-038. URL\nhttps:\/\/www.iso.ort\/tandard\/56426.html"},{"key":"242_CR27","doi-asserted-by":"crossref","unstructured":"Daniela Kaufmann, Paul Beame, Armin Biere & Jakob Nordstr\n\u00f6m (2022). Adding Dual Variables to Algebraic Reasoning for Gate-\nLevel Multiplier Verification. In Proceedings of the 25th Design, Automation\nand Test in Europe Conference (DATE\u201922).","DOI":"10.23919\/DATE54114.2022.9774587"},{"key":"242_CR28","doi-asserted-by":"crossref","unstructured":"Daniela Kaufmann & Armin Biere (2020). Nullstellensatz-Proofs\nfor Multiplier Verification. In Proceedings of the 22nd International\nWorkshop on Computer Algebra in Scientific Computing (CASC\u201920) ,\n368\u2013389.","DOI":"10.1007\/978-3-030-60026-6_21"},{"key":"242_CR29","doi-asserted-by":"crossref","unstructured":"Daniela Kaufmann, Armin Biere & Manuel Kauers (2019). Verifying\nLarge Multipliers by Combining SAT and Computer Algebra. In\nProceedings of the 2019 Formal Methods in Computer Aided Design\n(FMCAD\u201919), 28\u201336.","DOI":"10.23919\/FMCAD.2019.8894250"},{"key":"242_CR30","doi-asserted-by":"crossref","unstructured":"Daniela Kaufmann, Armin Biere & Manuel Kauers (2020).\nFrom DRUP to PAC and Back. In Proceedings of the 2020 Design,\nAutomation & Test in Europe Conference & Exhibition (DATE\u201920),\n654\u2013657","DOI":"10.23919\/DATE48585.2020.9116276"},{"key":"242_CR31","doi-asserted-by":"crossref","unstructured":"T.Y Lam & K.H Leung (2000). On Vanishing Sums of Roots of Unity.\nJournal of Algebra 224(1), 91\u2013109.","DOI":"10.1006\/jabr.1999.8089"},{"key":"242_CR32","doi-asserted-by":"crossref","unstructured":"J. Lasserre (2001). An explicit exact SDP relaxation for nonlinear\n0-1 programs. Integer Programming and Combinatorial Optimization \n293\u2013303.","DOI":"10.1007\/3-540-45535-3_23"},{"key":"242_CR33","unstructured":"Massimo Lauria & Jakob Nordstr\u00f6m (2017). Graph Colouring is\nHard for Algorithms Based on Hilbert\u2019s Nullstellensatz and Gr\u00f6bner\nBases. In  Proceedings of the 32nd Computational Complexity Conference \n(CCC\u201917), volume 79, 2:1\u20132:20."},{"key":"242_CR34","unstructured":"Troy Lee, Anupam Prakash, Ronald de Wolf & Henry Yuen\n(2016). On the sum-of-squares degree of symmetric quadratic functions.\nIn Proceedings of the 31st Conference on Computational Complexity\n(CCC\u201916), volume 50 of LIPIcs. Leibniz Int. Proc. Inform., Art. No.\n17, 31."},{"key":"242_CR35","doi-asserted-by":"crossref","unstructured":"Jo\u00e3o. Marques-Silva & Karem A. Sakallah (1999). GRASP:\nA search algorithm for propositional satisfiability. Computers, IEEE\nTransactions on 48(5), 506\u2013521.","DOI":"10.1109\/12.769433"},{"key":"242_CR36","doi-asserted-by":"crossref","unstructured":"M.W. Moskewicz, C.F. Madigan, Y. Zhao, L. Zhang & S. Malik\n(2001). Chaff: Engineering an efficient SAT solver. In Proceedings of\nthe 38th annual Design Automation Conference (DAC\u201901), 530\u2013535.","DOI":"10.1145\/378239.379017"},{"key":"242_CR37","doi-asserted-by":"crossref","unstructured":"Pablo A. Parrilo (2003). Semidefinite programming relaxations for\nsemialgebraic problems. Mathematical programming 96(2), 293\u2013320.","DOI":"10.1007\/s10107-003-0387-5"},{"key":"242_CR38","unstructured":"Aaron Potechin (2020). Sum of Squares Bounds for the Ordering\nPrinciple. In  35th Computational Complexity Conference (CCC\u201920),\nvolume 169 of LIPIcs, 38:1\u201338:37."},{"key":"242_CR39","unstructured":"Susanna F. de Rezende, Massimo Lauria, Jakob Nordstr\u00f6m &\nDmitry Sokolov (2021). The Power of Negative Reasoning. In  Proceedings\nof the 36th Computational Complexity Conference (CCC\u201921),\nvolume 200 of LIPIcs, 40:1\u201340:24."},{"key":"242_CR40","doi-asserted-by":"crossref","unstructured":"Grant Schoenebeck (2008). Linear Level Lasserre Lower Bounds for\nCertain k-CSPs. In 49th Annual IEEE Symposium on Foundations of\nComputer Science (FOCS \u201908), 593\u2013602.","DOI":"10.1109\/FOCS.2008.74"},{"key":"242_CR41","doi-asserted-by":"crossref","unstructured":"Roman Smolensky (1987). Algebraic Methods in the Theory of Lower\nBounds for Boolean Circuit Complexity. In Proceedings of the 19th\nAnnual ACM Symposium on Theory of Computing (STOC\u201987), 77\u201382.\nACM.","DOI":"10.1145\/28395.28404"},{"key":"242_CR42","doi-asserted-by":"crossref","unstructured":"Dmitry Sokolov (2020). (Semi)Algebraic proofs over {\u00b11} variables.\nIn Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory\nof Computing (STOC\u201920).","DOI":"10.1145\/3357713.3384288"},{"key":"242_CR43","doi-asserted-by":"crossref","unstructured":"Madhur Tulsiani (2009). CSP gaps and reductions in the Lasserre hierarchy.\nIn  Proceedings of the 41st Annual ACM Symposium on Theory\nof Computing (STOC\u201909), 303\u2013312. ACM.","DOI":"10.1145\/1536414.1536457"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-023-00242-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-023-00242-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-023-00242-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,26]],"date-time":"2023-12-26T19:04:58Z","timestamp":1703617498000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-023-00242-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,12]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["242"],"URL":"https:\/\/doi.org\/10.1007\/s00037-023-00242-z","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[2023,11,12]]},"assertion":[{"value":"9 November 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 November 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"12"}}