Sum of squares bounds for the ordering principle

DOI10.4230/LIPIcs.CCC.2020.38OpenAlexW3046729927MaRDI QIDQ5092489

Aaron Potechin

Publication date: 21 July 2022

Full work available at URL: https://arxiv.org/abs/1812.01163

zbMATH Keywords

proof complexityordering principlesum of squares hierarchy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

On vanishing sums of roots of unity in polynomial calculus and sum-of-squares

Cites Work

• Unnamed Item
• Short proofs for tricky formulas
• Optimality of size-width tradeoffs for resolution
• Symmetric sums of squares over \(k\)-subset hypercubes
• Short resolution proofs for a sequence of tricky formulas
• Lower bounds for the polynomial calculus and the Gröbner basis algorithm
• A Nullstellensatz and a Positivstellensatz in semialgebraic geometry
• Optimality of size-degree tradeoffs for polynomial calculus
• Short proofs are narrow—resolution made simple
• Size-degree trade-offs for sums-of-squares and positivstellensatz proofs
• Hypercontractivity, sum-of-squares proofs, and their applications