Regular resolution lower bounds for the weak pigeonhole principle

DOI10.1145/380752.380821zbMath1323.03090OpenAlexW2006367699MaRDI QIDQ5175989

Toniann Pitassi, Ran Raz

Publication date: 27 February 2015

Published in: Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/380752.380821

Mathematics Subject Classification ID

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

Related Items (7)

Resolution lower bounds for perfect matching principles ⋮ Mutilated chessboard problem is exponentially hard for resolution ⋮ Resolution lower bounds for the weak functional pigeonhole principle. ⋮ The NP-hardness of finding a directed acyclic graph for regular resolution ⋮ A new proof of the weak pigeonhole principle ⋮ Time-Space Trade-offs in Resolution: Superpolynomial Lower Bounds for Superlinear Space ⋮ Lower bounds for the weak pigeonhole principle and random formulas beyond resolution

Cites Work

• A constant-factor approximation algorithm for the k -median problem (extended abstract)

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