2026-07-24T05:48:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16821 2024-03-06T10:58:25Z ddc:004 open_access

On Vanishing Sums of Roots of Unity in Polynomial Calculus and Sum-Of-Squares Bonacina, Ilario Galesi, Nicola Lauria, Massimo polynomial calculus sum-of-squares roots of unity knapsack Vanishing sums of roots of unity can be seen as a natural generalization of knapsack from Boolean variables to variables taking values over the roots of unity. We show that these sums are hard to prove for polynomial calculus and for sum-of-squares, both in terms of degree and size. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ilario Bonacina and Nicola Galesi and Massimo Lauria 2022 Is Part Of LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2022.23 urn:nbn:de:0030-drops-168211 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.23 eng https://creativecommons.org/licenses/by/4.0/legalcode