Export Citations
2 Results for: Keyword: random CNF
Save this search
Please login to be able to save your searches and receive alerts for new content matching your search criteria.
Searched The ACM Guide to Computing Literature (3,823,136 records)|Limit your search to The ACM Full-Text Collection (772,319 records)
Select All
- research-articleJune 2024
Random (log 𝑛)-CNF Are Hard for Cutting Planes (Again)
STOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of ComputingPages 2008–2015https://doi.org/10.1145/3618260.3649636The random Δ-CNF model is one of the most important distribution over Δ-SAT instances. It is closely connected to various areas of computer science, statistical physics, and is a benchmark for satisfiability algorithms. Fleming, Pankratov, Pitassi, and ...
- articleDecember 2006
Linear Upper Bounds for Random Walk on Small Density Random $3$-CNFs
SIAM Journal on Computing (SICOMP), Volume 36, Issue 5Pages 1248–1263https://doi.org/10.1137/S0097539704440107We analyze the efficiency of the random walk algorithm on random $3$-CNF instances and prove linear upper bounds on the running time of this algorithm for small clause density, less than $1.63$. This is the first subexponential upper bound on the ...