Dual weak pigeonhole principle, Boolean complexity, and derandomization
Top Cited Papers
- 31 October 2004
- journal article
- Published by Elsevier BV in Annals of Pure and Applied Logic
- Vol. 129 (1-3), 1-37
- https://doi.org/10.1016/j.apal.2003.12.003
Abstract
No abstract availableKeywords
This publication has 11 references indexed in Scilit:
- A model-theoretic characterization of the weak pigeonhole principleAnnals of Pure and Applied Logic, 2002
- A New Proof of the Weak Pigeonhole PrincipleJournal of Computer and System Sciences, 2002
- On the weak pigeonhole principleFundamenta Mathematicae, 2001
- Jan Krajíček. Bounded arithmetic, propositional logic, and complexity theory. Encyclopedia of mathematics and its applications, vol. 60. Cambridge University Press, Cambridge, New York, and Oakleigh, Victoria, 1995, xiv + 343 pp.The Journal of Symbolic Logic, 1999
- Some Consequences of Cryptographical Conjectures forS12and EFInformation and Computation, 1998
- Proof complexity in algebraic systems and bounded depth Frege systems with modular countingcomputational complexity, 1996
- Hardness vs randomnessJournal of Computer and System Sciences, 1994
- Quantified propositional calculi and fragments of bounded arithmeticMathematical Logic Quarterly, 1990
- Provability of the pigeonhole principle and the existence of infinitely many primesThe Journal of Symbolic Logic, 1988
- Existence and feasibility in arithmeticThe Journal of Symbolic Logic, 1971