Regular resolution lower bounds for the weak pigeonhole principle

DOI10.1007/S00493-004-0029-4MaRDI QIDQ558246zbMATH OpenOpenAlexFDO

Authors Toniann Pitassi, Ran Raz

Publication date 5 July 2005

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00493-004-0029-4

zbMATH Keywords

complexity of resolution proofsweak pigeonhole principle

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)

Recommendations

• Regular resolution lower bounds for the weak pigeonhole principle
• Resolution lower bounds for the weak pigeonhole principle
• Resolution lower bounds for the weak functional pigeonhole principle.
• Resolution proofs of generalized pigeonhole principles
• scientific article; zbMATH DE number 1223618

Cited in

(10)

• scientific article; zbMATH DE number 7561756 (Why is no real title available?)
• Approximate Euler characteristic, dimension, and weak pigeonhole principles
• Resolution lower bounds for the weak pigeonhole principle
• Resolution lower bounds for the weak functional pigeonhole principle.
• Width versus size in resolution proofs
• On the weak pigeonhole principle
• Propositional proof complexity
• Regular resolution lower bounds for the weak pigeonhole principle
• scientific article; zbMATH DE number 1789924 (Why is no real title available?)
• Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution

This page was built for publication: Regular resolution lower bounds for the weak pigeonhole principle

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