A sharp threshold in proof complexity

DOI10.1145/380752.380820zbMath1323.03088OpenAlexW2143404729MaRDI QIDQ5175988

No author found.

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: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.2995

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of proofs (03F20)

Related Items

The state of SAT ⋮ Cores in random hypergraphs and Boolean formulas ⋮ Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas ⋮ Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances ⋮ Random Instances of W[2-Complete Problems: Thresholds, Complexity, and Algorithms] ⋮ Restarts and exponential acceleration of the Davis-Putnam-Loveland-Logemann algorithm: A large deviation analysis of the generalized unit clause heuristic for random 3-SAT ⋮ The satisfiability threshold for randomly generated binary constraint satisfaction problems ⋮ On the relation among answer set solvers ⋮ The probabilistic analysis of a greedy satisfiability algorithm ⋮ Hard satisfiable instances for DPLL-type algorithms

Cites Work

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