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
(36)- Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
- Characterizing propositional proofs as noncommutative formulas
- Reflections on Proof Complexity and Counting Principles
- Resolution and the binary encoding of combinatorial principles
- scientific article; zbMATH DE number 7561756 (Why is no real title available?)
- 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
- Exponential resolution lower bounds for weak pigeonhole principle and perfect matching formulas over sparse graphs
- Incompleteness in the finite domain
- Feasibly constructive proofs of succinct weak circuit lower bounds
- Learning algorithms from circuit lower bounds
- Lower bounds for DNF-refutations of a relativized weak pigeonhole principle
- Pseudorandom Generators in Propositional Proof Complexity
- The treewidth of proofs
- A proof complexity generator
- Shrinkage of decision lists and DNF formulas
- On minimal unsatisfiability and time-space trade-offs for k-DNF resolution
- Circuit lower bounds in bounded arithmetics
- Hardness magnification near state-of-the-art lower bounds
- 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
- Randomness buys depth for approximate counting
- On the correspondence between arithmetic theories and propositional proof systems – a survey
- On the consistency of circuit lower bounds for non-deterministic time
- Towards PNP from extended Frege lower bounds
- Stretching demi-bits and nondeterministic-secure pseudorandomness
- Hardness magnification near state-of-the-art lower bounds
- A remark on pseudo proof systems and hard instances of the satisfiability problem
- Random resolution refutations
- A framework for space complexity in algebraic proof systems
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)
