A Better Algorithm for Random k-SAT

DOI10.1137/09076516XzbMath1209.68345arXiv0902.3583MaRDI QIDQ5390578

Amin Coja-Oghlan

Publication date: 4 April 2011

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0902.3583

zbMATH Keywords

phase transitionsefficient algorithmsrandom structures\(k\)-SAT

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (19)

Deep learning: a statistical viewpoint ⋮ On independent sets in random graphs ⋮ An algorithm for random signed 3-SAT with intervals ⋮ Random Instances of Problems in NP – Algorithms and Statistical Physics ⋮ A concentration inequality for the facility location problem ⋮ Counting Solutions to Random CNF Formulas ⋮ The asymptotic \(k\)-SAT threshold ⋮ Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem ⋮ Random hypergraphs and property B ⋮ Network models: structure and function. Abstracts from the workshop held December 10--16, 2017 ⋮ The large deviations of the whitening process in random constraint satisfaction problems ⋮ Satisfiability threshold for power law random 2-SAT in configuration model ⋮ The set of solutions of random XORSAT formulae ⋮ Belief propagation on the random \(k\)-SAT model ⋮ Biased landscapes for random constraint satisfaction problems ⋮ On Super Strong ETH ⋮ Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion ⋮ Unnamed Item ⋮ Walksat Stalls Well Below Satisfiability

This page was built for publication: A Better Algorithm for Random k-SAT