ECCC-Report TR22-105https://eccc.weizmann.ac.il/report/2022/105Comments and Revisions published for TR22-105en-usMon, 18 Jul 2022 16:04:40 +0300
Paper TR22-105
| On vanishing sums of roots of unity in polynomial calculus and sum-of-squares |
Ilario Bonacina,
Nicola Galesi,
Massimo Lauria
https://eccc.weizmann.ac.il/report/2022/105Vanishing 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.Mon, 18 Jul 2022 16:04:40 +0300https://eccc.weizmann.ac.il/report/2022/105