ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION
From MaRDI portal
Publication:3094358
Recommendations
- scientific article; zbMATH DE number 1670535
- The complexity of constructing pseudorandom generators from hard functions
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
- Verifiable Computation and Succinct Arguments for NP
- Pseudorandom Generators in Propositional Proof Complexity
- Hardness hypotheses, derandomization, and circuit complexity
- FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
- On basing size-verifiable one-way functions on NP-hardness
- Towards NP-P via proof complexity and search
- Towards NP-P via proof complexity and search
Cites work
- Bounded arithmetic and the polynomial hierarchy
- Computational Complexity
- Diagonalization in proof complexity
- Dual weak pigeonhole principle, Boolean complexity, and derandomization
- Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
- Foundations of Cryptography
- Hardness vs randomness
- Logical Foundations of Proof Complexity
- Nisan-Wigderson generators in proof systems with forms of interpolation
- On the weak pigeonhole principle
- Propositional proof systems, the consistency of first order theories and the complexity of computations
- Some consequences of cryptographical conjectures for \(S_2^1\) and EF
- Tautologies from pseudo-random generators
- The relative efficiency of propositional proof systems
Cited in
(14)- Pseudo-finite hard instances for a student-teacher game with a Nisan-Wigderson generator
- A proof complexity generator
- Incompleteness in the finite domain
- Pseudorandom Generators in Propositional Proof Complexity
- Circuit lower bounds in bounded arithmetics
- A limitation on the KPT interpolation
- Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
- ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS
- Failure of feasible disjunction property for k-DNF resolution and NP-hardness of automating it
- On the unprovability of circuit size bounds in intuitionistic \(\mathsf{S}^1_2\)
- Learning algorithms from circuit lower bounds
- On \(\mathrm{NP} \cap \mathrm{coNP}\) proof complexity generators
- Iterated lower bound formulas: a diagonalization-based approach to proof complexity
- Short propositional refutations for dense random 3CNF formulas
This page was built for publication: ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3094358)
