Regular resolution lower bounds for the weak pigeonhole principle

DOI10.1007/S00493-004-0029-4zbMATH Open1063.03044OpenAlexW2001378190MaRDI QIDQ558246FDOQ558246

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

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

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)

Cited In (8)

• Title not available (Why is that?)
• Approximate Euler characteristic, dimension, and weak pigeonhole principles
• Resolution lower bounds for the weak functional pigeonhole principle.
• Width versus size in resolution proofs
• Propositional proof complexity
• On the weak pigeonhole principle
• Title not available (Why is that?)
• 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)