Solving random satisfiable 3CNF formulas in expected polynomial time

DOI10.1145/1109557.1109608zbMath1192.68370OpenAlexW4250225190MaRDI QIDQ3581497

Dan Vilenchik, Michael Krivelevich

Publication date: 16 August 2010

Published in: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1109557.1109608

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (10)

Time complexity analysis of evolutionary algorithms on random satisfiable \(k\)-CNF formulas ⋮ On the Complexity of Random Satisfiability Problems with Planted Solutions ⋮ Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability ⋮ A spectral technique for random satisfiable 3CNF formulas ⋮ On the security of Goldreich's one-way function ⋮ A Spectral Method for MAX2SAT in the Planted Solution Model ⋮ Optimal testing for planted satisfiability problems ⋮ Unnamed Item ⋮ On Super Strong ETH ⋮ Solving non-uniform planted and filtered random SAT formulas greedily

This page was built for publication: Solving random satisfiable 3CNF formulas in expected polynomial time