We introduce a novel take on sum-of-squares that is ableto reason with complex numbers and still make use of polynomial inequalities.This proof system might be of independent interest since itallows to represent multivalued domains both with Boolean and Fourierencoding. We show degree and size lower bounds in this system for anatural generalization of knapsack: the vanishing sums of roots of unity.These lower bounds naturally apply to polynomial calculus as-well.
On vanishing sums of roots of unity in polynomial calculus and sum-of-squares / Bonacina, Ilario; Galesi, Nicola; Lauria, Massimo. - In: COMPUTATIONAL COMPLEXITY. - ISSN 1016-3328. - 32:2(2023), pp. 1-45. [10.1007/s00037-023-00242-z]
On vanishing sums of roots of unity in polynomial calculus and sum-of-squares
Ilario Bonacina
;Nicola Galesi
;Massimo Lauria
2023
Abstract
We introduce a novel take on sum-of-squares that is ableto reason with complex numbers and still make use of polynomial inequalities.This proof system might be of independent interest since itallows to represent multivalued domains both with Boolean and Fourierencoding. We show degree and size lower bounds in this system for anatural generalization of knapsack: the vanishing sums of roots of unity.These lower bounds naturally apply to polynomial calculus as-well.| File | Dimensione | Formato | |
|---|---|---|---|
|
Bonacina_vanishing-sums_2023.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
612.64 kB
Formato
Adobe PDF
|
612.64 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
