Dual weak pigeonhole principle, Boolean complexity, and derandomization

DOI10.1016/j.apal.2003.12.003zbMath1057.03047OpenAlexW2116335551WikidataQ115920200 ScholiaQ115920200MaRDI QIDQ1887654

Emil Jeřábek

Publication date: 22 November 2004

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2003.12.003

zbMATH Keywords

bounded arithmeticcircuit complexityrandomized algorithmsderandomizationweak pigeonhole principlep-time functions

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30) Complexity of proofs (03F20)

Related Items (27)

The NP Search Problems of Frege and Extended Frege Proofs ⋮ Proofs with monotone cuts ⋮ Short Proofs of the Kneser-Lovász Coloring Principle ⋮ Short proofs of the Kneser-Lovász coloring principle ⋮ Circuit principles and weak pigeonhole variants ⋮ FRAGMENTS OF APPROXIMATE COUNTING ⋮ Propositional Proofs in Frege and Extended Frege Systems (Abstract) ⋮ Typical forcings, NP search problems and an extension of a theorem of Riis ⋮ Collapsing modular counting in bounded arithmetic and constant depth propositional proofs ⋮ ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS ⋮ Circuit lower bounds in bounded arithmetics ⋮ Witnessing matrix identities and proof complexity ⋮ Abelian groups and quadratic residues in weak arithmetic ⋮ Approximate counting in bounded arithmetic ⋮ Feasibly constructive proofs of succinct weak circuit lower bounds ⋮ Upper and lower Ramsey bounds in bounded arithmetic ⋮ Understanding cutting planes for QBFs ⋮ On the correspondence between arithmetic theories and propositional proof systems – a survey ⋮ Short propositional refutations for dense random 3CNF formulas ⋮ Substitution Frege and extended Frege proof systems in non-classical logics ⋮ ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION ⋮ Approximate counting by hashing in bounded arithmetic ⋮ Unnamed Item ⋮ On the proof complexity of logics of bounded branching ⋮ Structures interpretable in models of bounded arithmetic ⋮ Short Proofs for the Determinant Identities ⋮ Hardness and optimality in QBF proof systems modulo NP

Cites Work

• Hardness vs randomness
• Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
• Some consequences of cryptographical conjectures for \(S_2^1\) and EF
• A model-theoretic characterization of the weak pigeonhole principle
• On the weak pigeonhole principle
• Quantified propositional calculi and fragments of bounded arithmetic
• Provability of the pigeonhole principle and the existence of infinitely many primes
• Existence and feasibility in arithmetic
• A new proof of the weak pigeonhole principle
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Dual weak pigeonhole principle, Boolean complexity, and derandomization