The strength of multilinear proofs

DOI10.1007/S00037-008-0246-0zbMATH Open1174.03025OpenAlexW2074020517MaRDI QIDQ1024659FDOQ1024659

Authors Ran Raz, Iddo Tzameret

Publication date 17 June 2009

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00037-008-0246-0

zbMATH Keywords

proof complexitypolynomial calculuspigeonhole principlemultilinear arithmetical formulasTseitin tautologies

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Complexity of proofs (03F20)

Recommendations

• The proof complexity of linear algebra
• Proof of Rueppel's linear complexity conjecture (Corresp.)
• Nullstellensatz-proofs for multiplier verification
• A sharp threshold in proof complexity
• On the complexity of cutting-plane proofs
• Resolution over linear equations and multilinear proofs
• Complexity of Null- and Positivstellensatz proofs
• On proving parameterized size lower bounds for multilinear algebraic models
• On proving parameterized size lower bounds for multilinear algebraic models
• Proof Complexity and the Kneser-Lovász Theorem

Cited in

(7)

• Algebraic proofs over noncommutative formulas
• Algebraic proof systems over formulas.
• Resolution over linear equations and multilinear proofs
• Characterizing propositional proofs as noncommutative formulas
• scientific article; zbMATH DE number 7471587 (Why is no real title available?)
• The surprising power of constant depth algebraic proofs
• Proof complexity lower bounds from algebraic circuit complexity

This page was built for publication: The strength of multilinear proofs

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