Pseudorandom generators hard for k-DNF resolution and polynomial calculus resolution
From MaRDI portal
Publication:2255289
DOI10.4007/ANNALS.2015.181.2.1zbMATH Open1376.03055OpenAlexW2114400329MaRDI QIDQ2255289FDOQ2255289
Authors: Alexander Razborov 
Publication date: 9 February 2015
Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4007/annals.2015.181.2.1
Recommendations
- The complexity of constructing pseudorandom generators from hard functions
- Random CNF's are hard for the polynomial calculus
- Pseudorandomness for read-\(k\) DNF formulas
- Pseudorandom Generators in Propositional Proof Complexity
- Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
- scientific article; zbMATH DE number 2081094
- Derandomization from Algebraic Hardness
- scientific article; zbMATH DE number 7150624
- scientific article; zbMATH DE number 7250153
- On linear-size pseudorandom generators and hardcore functions
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Hardness vs randomness
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- Some consequences of cryptographical conjectures for \(S_2^1\) and EF
- 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 Complexity of Propositional Proofs
- CREW PRAM<scp>s</scp> and Decision Trees
- Lower bounds for cutting planes proofs with small coefficients
- Title not available (Why is that?)
- Natural proofs
- Candidate One-Way Functions Based on Expander Graphs
- Title not available (Why is that?)
- Pseudorandom Generators in Propositional Proof Complexity
- Quantum lower bounds by polynomials
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Poisson approximation for large deviations
- Randomness conductors and constant-degree lossless expanders
- A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
- Lower bounds for the polynomial calculus
- Resolution lower bounds for perfect matching principles
- On the weak pigeonhole principle
- On Interpolation and Automatization for Frege Systems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
- Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
- Linear gaps between degrees for the polynomial calculus modulo distinct primes
- Random CNF's are hard for the polynomial calculus
- Lower bounds for the weak pigeonhole principle and random formulas beyond resolution
- An exponential separation between the parity principle and the pigeonhole principle
- Space Complexity in Propositional Calculus
- Title not available (Why is that?)
- Regular resolution lower bounds for the weak pigeonhole principle
- Title not available (Why is that?)
- Tautologies from pseudo-random generators
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (28)
- Reflections on Proof Complexity and Counting Principles
- Resolution and the binary encoding of combinatorial principles
- Title not available (Why is that?)
- Proof complexity and the binary encoding of combinatorial principles
- Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
- ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION
- Random CNF's are hard for the polynomial calculus
- Substitutions into propositional tautologies
- Feasibly constructive proofs of succinct weak circuit lower bounds
- Pseudorandom Generators in Propositional Proof Complexity
- The treewidth of proofs
- Characterizing Propositional Proofs as Noncommutative Formulas
- Circuit lower bounds in bounded arithmetics
- Title not available (Why is that?)
- Tautologies from pseudo-random generators
- Separation results for the size of constant-depth propositional proofs
- Hardness assumptions in the foundations of theoretical computer science
- ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS
- Propositional proof complexity
- On the correspondence between arithmetic theories and propositional proof systems – a survey
- Randomness buys depth for approximate counting
- INCOMPLETENESS IN THE FINITE DOMAIN
- On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution
- Hardness magnification near state-of-the-art lower bounds
- Random resolution refutations
- A framework for space complexity in algebraic proof systems
- LOWER BOUNDS FOR DNF-REFUTATIONS OF A RELATIVIZED WEAK PIGEONHOLE PRINCIPLE
- Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
This page was built for publication: Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2255289)
