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

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

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)

Cited In (5)

• Characterizing Propositional Proofs as Noncommutative Formulas
• Algebraic proofs over noncommutative formulas
• Resolution over linear equations and multilinear proofs
• Title not available (Why is that?)
• Algebraic proof systems over formulas.

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)