Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2022.23
URN: urn:nbn:de:0030-drops-168211
URL: https://drops.dagstuhl.de/opus/volltexte/2022/16821/
Bonacina, Ilario ; Galesi, Nicola ; Lauria, Massimo
On Vanishing Sums of Roots of Unity in Polynomial Calculus and Sum-Of-Squares
| pdf-format: |
|
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.
BibTeX - Entry
@InProceedings{bonacina_et_al:LIPIcs.MFCS.2022.23,
author = {Bonacina, Ilario and Galesi, Nicola and Lauria, Massimo},
title = {{On Vanishing Sums of Roots of Unity in Polynomial Calculus and Sum-Of-Squares}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {23:1--23:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16821},
URN = {urn:nbn:de:0030-drops-168211},
doi = {10.4230/LIPIcs.MFCS.2022.23},
annote = {Keywords: polynomial calculus, sum-of-squares, roots of unity, knapsack}
}
| Keywords: | polynomial calculus, sum-of-squares, roots of unity, knapsack | |
| Seminar: | 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 22.08.2022 |
