scientific article; zbMATH DE number 2087215

MaRDI QIDQ4737899zbMATH OpenFDO

Authors Alexander Razborov

Publication date 11 August 2004

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

zbMATH Keywords

survey

Mathematics Subject Classification ID

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

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

(18)

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

This page was built for publication:

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