Proof complexity of pigeonhole principles

DOI10.1007/3-540-46011-X_8MaRDI QIDQ4737899zbMATH OpenFDO

Authors Alexander Razborov

Publication date 11 August 2004

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2295/22950100.htm

zbMATH Keywords

survey

Mathematics Subject Classification ID

Complexity of proofs (03F20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• The complexity of the pigeonhole principle
• On the weak pigeonhole principle
• Resolution proofs of generalized pigeonhole principles
• A new proof of the weak pigeonhole principle
• Count\((q)\) versus the pigeon-hole principle

Cited in

(22)

• Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus
• The treewidth of proofs
• Large clique is hard on average for resolution
• Expander construction in \(\mathrm{VNC}^1\)
• Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
• Partially definable forcing and bounded arithmetic
• Rank bounds for a hierarchy of Lovász and Schrijver
• Resolution and the binary encoding of combinatorial principles
• scientific article; zbMATH DE number 7561756 (Why is no real title available?)
• scientific article; zbMATH DE number 7300350 (Why is no real title available?)
• Phase transitions related to the pigeonhole principle
• Exploiting symmetry in SMT problems
• On the proof complexity of Paris-Harrington and off-diagonal Ramsey tautologies
• Propositional proof complexity
• Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas
• Perfect matching in random graphs is as hard as Tseitin
• Polynomial calculus space and resolution width
• Exponential resolution lower bounds for weak pigeonhole principle and perfect matching formulas over sparse graphs
• A generalized method for proving polynomial calculus degree lower bounds
• Refuting perfect matchings in spectral expanders is hard
• Short proofs of the pigeonhole formulas based on the connection method
• Resolution over linear equations and multilinear proofs

This page was built for publication: Proof complexity of pigeonhole principles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4737899)