Dual weak pigeonhole principle, Boolean complexity, and derandomization
type: Item
instance of: scholarly article
title: Dual weak pigeonhole principle, Boolean complexity, and derandomization
zbMATH Open document ID: 1057.03047
author: Emil Jeřábek
published in: Annals of Pure and Applied Logic
publication date: 2004-11-22T00:00:00Z
Mathematics Subject Classification ID: 03F20
Mathematics Subject Classification ID: 03F30
zbMATH DE Number: 2117324
zbMATH Keywords: derandomization
zbMATH Keywords: weak pigeonhole principle
zbMATH Keywords: p-time functions
zbMATH Keywords: randomized algorithms
zbMATH Keywords: bounded arithmetic
zbMATH Keywords: circuit complexity
MaRDI profile type: Publication
full work available at URL: j.apal.2003.12.003
OpenAlex ID: W2116335551
cites work: Q3794177
cites work: Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
cites work: Q4133141
cites work: Q4856172
cites work: On the weak pigeonhole principle
cites work: Quantified propositional calculi and fragments of bounded arithmetic
cites work: Some consequences of cryptographical conjectures for \(S_2^1\) and EF
cites work: A new proof of the weak pigeonhole principle
cites work: Hardness vs randomness
cites work: Existence and feasibility in arithmetic
cites work: Provability of the pigeonhole principle and the existence of infinitely many primes
cites work: A model-theoretic characterization of the weak pigeonhole principle
Wikidata QID: Q115920200
DOI: 10.1016/J.APAL.2003.12.003
description: scientific article; zbMATH DE number 2117324