Nisan-Wigderson generators in proof systems with forms of interpolation

DOI10.1002/malq.201010012zbMath1252.03132OpenAlexW2061209875MaRDI QIDQ3170558

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

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

Related Items (1)

ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION

Cites Work

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

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