Pseudorandom Generators in Propositional Proof Complexity
From MaRDI portal
Publication:4651526
DOI10.1137/S0097539701389944zbMath1096.03070MaRDI QIDQ4651526
Eli Ben-Sasson, Michael Alekhnovich, Avi Wigderson, Alexander A. Razborov
Publication date: 21 February 2005
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Complexity of computation (including implicit computational complexity) (03D15) Complexity of proofs (03F20)
Related Items (33)
Resolution lower bounds for perfect matching principles ⋮ Nisan-Wigderson generators in proof systems with forms of interpolation ⋮ Substitutions into propositional tautologies ⋮ A dichotomy for local small-bias generators ⋮ Hardness assumptions in the foundations of theoretical computer science ⋮ Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas ⋮ Randomized feasible interpolation and monotone circuits with a local oracle ⋮ Characterizing Propositional Proofs as Noncommutative Formulas ⋮ Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms ⋮ Resolution lower bounds for the weak functional pigeonhole principle. ⋮ Spanoids---An Abstraction of Spanning Structures, and a Barrier for LCCs ⋮ Expander graphs and their applications ⋮ ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS ⋮ The complexity of inverting explicit Goldreich's function by DPLL algorithms ⋮ More on average case vs approximation complexity ⋮ Satisfiability, branch-width and Tseitin tautologies ⋮ Special issue in memory of Misha Alekhnovich. Foreword ⋮ Lower bounds for \(k\)-DNF resolution on random 3-CNFs ⋮ The complexity of proving that a graph is Ramsey ⋮ Algebraic proofs over noncommutative formulas ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A combinatorial characterization of resolution width ⋮ On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography ⋮ Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution ⋮ Feasibly constructive proofs of succinct weak circuit lower bounds ⋮ Unnamed Item ⋮ On the correspondence between arithmetic theories and propositional proof systems – a survey ⋮ Proof Complexity of Non-classical Logics ⋮ Candidate One-Way Functions Based on Expander Graphs ⋮ Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs ⋮ Adventures in monotone complexity and TFNP ⋮ Hardness magnification near state-of-the-art lower bounds
This page was built for publication: Pseudorandom Generators in Propositional Proof Complexity
