Pseudorandom generators hard for k-DNF resolution and polynomial calculus resolution
From MaRDI portal
Publication:2255289
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
Cites work
- scientific article; zbMATH DE number 3960854 (Why is no real title available?)
- scientific article; zbMATH DE number 1215500 (Why is no real title available?)
- scientific article; zbMATH DE number 1256733 (Why is no real title available?)
- scientific article; zbMATH DE number 2174386 (Why is no real title available?)
- scientific article; zbMATH DE number 1361469 (Why is no real title available?)
- scientific article; zbMATH DE number 2087215 (Why is no real title available?)
- scientific article; zbMATH DE number 1860652 (Why is no real title available?)
- scientific article; zbMATH DE number 2102736 (Why is no real title available?)
- scientific article; zbMATH DE number 806753 (Why is no real title available?)
- scientific article; zbMATH DE number 819737 (Why is no real title available?)
- A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
- An exponential separation between the parity principle and the pigeonhole principle
- CREW PRAM<scp>s</scp> and Decision Trees
- Candidate one-way functions based on expander graphs
- Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
- Hardness vs randomness
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- Linear gaps between degrees for the polynomial calculus modulo distinct primes
- Lower bounds for cutting planes proofs with small coefficients
- Lower bounds for resolution and cutting plane proofs and monotone computations
- Lower bounds for the polynomial calculus
- Lower bounds for the weak pigeonhole principle and random formulas beyond resolution
- Natural proofs
- On Interpolation and Automatization for Frege Systems
- On the weak pigeonhole principle
- Poisson approximation for large deviations
- Pseudorandom Generators in Propositional Proof Complexity
- Quantum lower bounds by polynomials
- Random CNF's are hard for the polynomial calculus
- Randomness conductors and constant-degree lossless expanders
- Regular resolution lower bounds for the weak pigeonhole principle
- Resolution lower bounds for perfect matching principles
- Some consequences of cryptographical conjectures for \(S_2^1\) and EF
- Space Complexity in Propositional Calculus
- Tautologies from pseudo-random generators
- The Complexity of Propositional Proofs
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
Cited in
(30)- Circuit lower bounds in bounded arithmetics
- Reflections on Proof Complexity and Counting Principles
- ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION
- Hardness magnification near state-of-the-art lower bounds
- Tautologies from pseudo-random generators
- A framework for space complexity in algebraic proof systems
- A remark on pseudo proof systems and hard instances of the satisfiability problem
- Characterizing propositional proofs as noncommutative formulas
- Hardness magnification near state-of-the-art lower bounds
- Lower bounds for DNF-refutations of a relativized weak pigeonhole principle
- scientific article; zbMATH DE number 7561756 (Why is no real title available?)
- ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS
- A proof complexity generator
- On the correspondence between arithmetic theories and propositional proof systems – a survey
- Incompleteness in the finite domain
- The treewidth of proofs
- Proof complexity and the binary encoding of combinatorial principles
- On minimal unsatisfiability and time-space trade-offs for \(k\)-DNF resolution
- Propositional proof complexity
- Substitutions into propositional tautologies
- Separation results for the size of constant-depth propositional proofs
- Randomness buys depth for approximate counting
- Pseudorandom Generators in Propositional Proof Complexity
- Feasibly constructive proofs of succinct weak circuit lower bounds
- Random resolution refutations
- Hardness assumptions in the foundations of theoretical computer science
- Random CNF's are hard for the polynomial calculus
- 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
- Resolution and the binary encoding of combinatorial principles
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)
