Nisan-Wigderson generators in proof systems with forms of interpolation

DOI10.1002/MALQ.201010012MaRDI QIDQ3170558zbMATH OpenOpenAlexFDO

Authors Ján Pich

Publication date 27 September 2011

Published in Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/malq.201010012

zbMATH Keywords

proof complexityfeasible interpolationNisan-Wigderson generator

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20) Complexity of computation (including implicit computational complexity) (03D15)

Cites work

• Diagonalization in proof complexity
• Hardness vs randomness
• Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
• Lower bounds for resolution and cutting plane proofs and monotone computations
• On the weak pigeonhole principle
• Pseudorandom Generators in Propositional Proof Complexity

Cited in

(3)

• A note on the strong and weak generative powers of formal systems
• ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION
• Learning algorithms from circuit lower bounds

This page was built for publication: Nisan-Wigderson generators in proof systems with forms of interpolation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3170558)