Name
Abstract | ||
|---|---|---|
The random k-SAT model is the most important and well-studied distribution over k-SAT instances. It is closely connected to statistical physics and is a benchmark for satisfiability algorithms. We show that when k = u0026#x398;(log n), any Cutting Planes refutation for random k-SAT requires exponential size in the interesting regime where the number of clauses guarantees that the formula is unsatisfiable with high probability. |
Year | Venue | Field |
|---|---|---|
2017 | FOCS | Boolean function,Binary logarithm,Discrete mathematics,Combinatorics,Exponential function,Satisfiability,Interpolation,Mathematics |
DocType | Citations | PageRank |
Conference | 1 | 0.35 |
References | Authors | |
13 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Noah Fleming | 1 | 1 | 2.71 |
| Denis Pankratov | 2 | 71 | 7.81 |
| Toniann Pitassi | 3 | 2282 | 155.18 |
| Robert Robere | 4 | 11 | 4.34 |