Resolution over linear equations modulo two
From MaRDI portal
Publication:2334112
DOI10.1016/j.apal.2019.102722OpenAlexW2969535762WikidataQ127350938 ScholiaQ127350938MaRDI QIDQ2334112
Dmitry Sokolov, Dmitry Itsykson
Publication date: 6 November 2019
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.2019.102722
Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Proof theory in general (including proof-theoretic semantics) (03F03) Complexity of proofs (03F20)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A satisfiability algorithm and average-case hardness for formulas over the full binary basis
- Near optimal seperation of tree-like and general resolution
- The depth of resolution proofs
- Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
- Resolution over linear equations and multilinear proofs
- Hard examples for the bounded depth Frege proof system
- Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms
- Hard satisfiable formulas for splittings by linear combinations
- Resolution lower bounds for perfect matching principles
- On multi-partition communication complexity
- An exponential separation between the parity principle and the pigeonhole principle
- Lower bounds for the polynomial calculus and the Gröbner basis algorithm
- Tight Upper Bound on Splitting by Linear Combinations for Pigeonhole Principle
- Lower Bounds for Splittings by Linear Combinations
- Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
- The Complexity of Inversion of Explicit Goldreich’s Function by DPLL Algorithms
- An Elementary Proof of a 3n − o(n) Lower Bound on the Circuit Complexity of Affine Dispersers
- Space Complexity in Propositional Calculus
- Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
- Improved Lower Bounds for Tree-Like Resolution over Linear Inequalities
- Hard examples for resolution
- The Probabilistic Communication Complexity of Set Intersection
- The relative efficiency of propositional proof systems
- Discretely ordered modules as a first-order extension of the cutting planes proof system
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- Short proofs are narrow—resolution made simple
- Randomized feasible interpolation and monotone circuits with a local oracle
- A Generalized Method for Proving Polynomial Calculus Degree Lower Bounds
- Some Subsystems of Constant-Depth Frege with Parity
- Search Problems in the Decision Tree Model
- Communication Complexity
- Communication lower bounds via critical block sensitivity
- An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams
- On the virtue of succinct proofs
- A Computing Procedure for Quantification Theory
- A machine program for theorem-proving
- Principles and Practice of Constraint Programming – CP 2004
This page was built for publication: Resolution over linear equations modulo two
