On vanishing sums of roots of unity in polynomial calculus and sum-of-squares
From MaRDI portal
Publication:6184293
DOI10.1007/s00037-023-00242-zOpenAlexW4388605079MaRDI QIDQ6184293
Nicola Galesi, Ilario Bonacina, Massimo Lauria
Publication date: 24 January 2024
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-023-00242-z
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sums of squares on the hypercube
- Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz
- Algebraic proof systems over formulas.
- Semidefinite programming relaxations for semialgebraic problems
- Sums of roots of unity vanishing modulo a prime
- Lower bounds for the polynomial calculus and the Gröbner basis algorithm
- On vanishing sums of roots of unity.
- On sums of roots of unity
- Nullstellensatz-proofs for multiplier verification
- Symmetric non-negative forms and sums of squares
- Graph-Coloring Ideals
- Optimality of size-degree tradeoffs for polynomial calculus
- Expressing Combinatorial Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz
- Trigonometric diophantine equations (On vanishing sums of roots of unity)
- GRASP: a search algorithm for propositional satisfiability
- Circuit Complexity, Proof Complexity, and Polynomial Identity Testing
- Size-degree trade-offs for sums-of-squares and positivstellensatz proofs
- Sum of squares bounds for the ordering principle
- Proof complexity meets algebra
- Semi-algebraic proofs, IPS lower bounds, and the τ-conjecture: can a natural number be negative?
- (Semi)Algebraic proofs over {±1} variables
- The Surprising Power of Constant Depth Algebraic Proofs
- CSP gaps and reductions in the lasserre hierarchy
- On the sum-of-squares degree of symmetric quadratic functions
- Linear gaps between degrees for the polynomial calculus modulo distinct primes
- Complexity of Positivstellensatz proofs for the knapsack
- The power of negative reasoning
