Sum of squares bounds for the ordering principle

DOI10.4230/LIPICS.CCC.2020.38MaRDI QIDQ5092489zbMATH OpenOpenAlexFDO

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

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)