TR22-105 Authors: Ilario Bonacina, Nicola Galesi, Massimo Lauria

Publication: 18th July 2022 16:04

Downloads: 102

Keywords:

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.