Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR22-105 | 18th July 2022 15:05

On vanishing sums of roots of unity in polynomial calculus and sum-of-squares

RSS-Feed




TR22-105
Authors: Ilario Bonacina, Nicola Galesi, Massimo Lauria
Publication: 18th July 2022 16:04
Downloads: 102
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint