Resolution over linear equations and multilinear proofs

DOI10.1016/J.APAL.2008.04.001zbMATH Open1161.03034OpenAlexW1982672583MaRDI QIDQ952492FDOQ952492

Authors: Ran Raz, Iddo Tzameret 

Publication date: 12 November 2008

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2008.04.001

Recommendations

• Lower Bounds for Splittings by Linear Combinations
• The strength of multilinear proofs
• scientific article; zbMATH DE number 3902027
• Circular (yet sound) proofs
• Several notes on the power of Gomory-Chvátal cuts
• Randomized feasible interpolation and monotone circuits with a local oracle
• On linear rewriting systems for Boolean logic and some applications to proof theory
• scientific article; zbMATH DE number 2119475
• scientific article; zbMATH DE number 515724
• A feasible interpolation for random resolution

zbMATH Keywords

cutting planesresolutionproof complexityalgebraic proof systemsfeasible interpolationmultilinear proofs

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Cites Work

• Title not available (Why is that?)
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• The relative efficiency of propositional proof systems
• Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
• Lower bounds for resolution and cutting plane proofs and monotone computations
• The monotone circuit complexity of Boolean functions
• Title not available (Why is that?)
• Lower bounds for cutting planes proofs with small coefficients
• Separation of multilinear circuit and formula size
• Title not available (Why is that?)
• Depth-3 arithmetic circuits over fields of characteristic zero
• The intractability of resolution
• On the weak pigeonhole principle
• Lower bounds to the size of constant-depth propositional proofs
• Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
• An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams
• Linear gaps between degrees for the polynomial calculus modulo distinct primes
• Lower bounds for the weak pigeonhole principle and random formulas beyond resolution
• Space Complexity in Propositional Calculus
• Title not available (Why is that?)
• Improved Lower Bounds for Tree-Like Resolution over Linear Inequalities
• Title not available (Why is that?)
• Title not available (Why is that?)
• Several notes on the power of Gomory-Chvátal cuts
• Multi-linear formulas for permanent and determinant are of super-polynomial size
• The strength of multilinear proofs
• Discretely ordered modules as a first-order extension of the cutting planes proof system

Cited In (13)

• Characterizing propositional proofs as noncommutative formulas
• On conversions from CNF to ANF
• On linear resolution
• Solving Linear Equations in *-continuous Action Lattices
• Resolution with counting: dag-like lower bounds and different moduli
• Monotone circuit lower bounds from resolution
• Resolution over linear equations modulo two
• Randomized feasible interpolation and monotone circuits with a local oracle
• Algebraic proofs over noncommutative formulas
• Randomized versus deterministic decision tree size
• Title not available (Why is that?)
• The strength of multilinear proofs
• Implicit resolution

This page was built for publication: Resolution over linear equations and multilinear proofs

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