Random resolution refutations
From MaRDI portal
Publication:2311546
DOI10.1007/s00037-019-00182-7zbMath1445.03063OpenAlexW2940838265MaRDI QIDQ2311546
Publication date: 10 July 2019
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7523/
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)
Related Items
Cites Work
- Unnamed Item
- The complexity of the pigeonhole principle
- Simplified lower bounds for propositional proofs
- Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
- On the weak pigeonhole principle
- FRAGMENTS OF APPROXIMATE COUNTING
- Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
- The Ordering Principle in a Fragment of Approximate Counting
- A feasible interpolation for random resolution
- The provably total search problems of bounded arithmetic
- Many hard examples for resolution
- The Probabilistic Communication Complexity of Set Intersection
- The relative efficiency of propositional proof systems
- Witnessing functions in bounded arithmetic and search problems
- Monotone circuits for matching require linear depth
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- Short proofs are narrow—resolution made simple
- A Note on Conservativity Relations among Bounded Arithmetic Theories
- Randomized feasible interpolation and monotone circuits with a local oracle
- An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
- NP search problems in low fragments of bounded arithmetic
- Computational Complexity
- On Independence of Variants of the Weak Pigeonhole Principle
