Sum of squares bounds for the ordering principle

DOI10.4230/LIPICS.CCC.2020.38OpenAlexW3046729927MaRDI QIDQ5092489FDOQ5092489

Authors: 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)

Cites Work

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

Cited In (3)

• Perfect matching in random graphs is as hard as Tseitin
• Proof complexity and the binary encoding of combinatorial principles
• On vanishing sums of roots of unity in polynomial calculus and sum-of-squares

This page was built for publication: Sum of squares bounds for the ordering principle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5092489)