Lower bounds for the weak pigeonhole principle and random formulas beyond resolution
type: Item
instance of: scholarly article
title: Lower bounds for the weak pigeonhole principle and random formulas beyond resolution
zbMATH Open document ID: 1012.03058
author: Albert Atserias
author: Maria Luisa Bonet
author: Juan Luis Esteban
published in: Information and Computation
publication date: 2003-01-14T00:00:00Z
Mathematics Subject Classification ID: 03F20
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 1853275
MaRDI profile type: Publication
OpenAlex ID: W2041857712
Wikidata QID: Q60512223
cites work: The monotone circuit complexity of Boolean functions
cites work: The efficiency of resolution and Davis-Putnam procedures
cites work: Short proofs are narrow—resolution made simple
cites work: Lower bounds for cutting planes proofs with small coefficients
cites work: Q4218929
cites work: Polynomial size proofs of the propositional pigeonhole principle
cites work: Resolution proofs of generalized pigeonhole principles
cites work: Many hard examples for resolution
cites work: Q3956129
cites work: The intractability of resolution
cites work: On the weak pigeonhole principle
cites work: A new proof of the weak pigeonhole principle
cites work: Provability of the pigeonhole principle and the existence of infinitely many primes
cites work: Regular resolution lower bounds for the weak pigeonhole principle
cites work: Lower bounds for resolution and cutting plane proofs and monotone computations
cites work: Resolution lower bounds for the weak pigeonhole principle
DBLP publication ID: journals/iandc/AtseriasBE02
DOI: 10.1006/INCO.2002.3114
description: scientific article; zbMATH DE number 1853275