Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Random Θ(log n)-CNFs are hard for Cutting Planes

Fleming, Noah LU orcid ; Pankratov, Denis ; Pitassi, Toniann and Robere, Robert (2022) In Journal of the ACM 69(3).
Abstract
The random k-SAT model is one of the most important and well-studied distributions over k-SAT instances. It is closely connected to statistical physics and is a benchmark for satisfiability algorithms. We show that when k=Θ(log n) , any Cutting Planes refutation for random k-SAT requires exponential length in the regime where the number of clauses guarantees that the formula is unsatisfiable with high probability.
Please use this url to cite or link to this publication:
author
; ; and
publishing date
type
Contribution to journal
publication status
published
subject
in
Journal of the ACM
volume
69
issue
3
pages
32 pages
publisher
Association for Computing Machinery (ACM)
ISSN
0004-5411
DOI
10.1145/3486680
language
English
LU publication?
no
id
503845c7-bad8-4a34-8fe0-4989fa3d379c
date added to LUP
2025-10-28 20:20:58
date last changed
2025-11-04 16:17:10
@article{503845c7-bad8-4a34-8fe0-4989fa3d379c,
  abstract     = {{The random k-SAT model is one of the most important and well-studied distributions over k-SAT instances. It is closely connected to statistical physics and is a benchmark for satisfiability algorithms. We show that when k=Θ(log n) , any Cutting Planes refutation for random k-SAT requires exponential length in the regime where the number of clauses guarantees that the formula is unsatisfiable with high probability.}},
  author       = {{Fleming, Noah and Pankratov, Denis and Pitassi, Toniann and Robere, Robert}},
  issn         = {{0004-5411}},
  language     = {{eng}},
  number       = {{3}},
  publisher    = {{Association for Computing Machinery (ACM)}},
  series       = {{Journal of the ACM}},
  title        = {{Random Θ(log n)-CNFs are hard for Cutting Planes}},
  url          = {{http://dx.doi.org/10.1145/3486680}},
  doi          = {{10.1145/3486680}},
  volume       = {{69}},
  year         = {{2022}},
}