Solving random satisfiable 3CNF formulas in expected polynomial time

DOI10.1145/1109557.1109608MaRDI QIDQ3581497zbMATH OpenOpenAlexFDO

Authors Michael Krivelevich, Dan Vilenchik

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

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

Cited in

(10)

• Solving non-uniform planted and filtered random SAT formulas greedily
• Optimal testing for planted satisfiability problems
• Time complexity analysis of evolutionary algorithms on random satisfiable k-CNF formulas
• A spectral technique for random satisfiable 3CNF formulas
• On the security of Goldreich's one-way function
• On the complexity of random satisfiability problems with planted solutions
• Generating weighted MAX-2-SAT instances with frustrated loops: an RBM case study
• A Spectral Method for MAX2SAT in the Planted Solution Model
• On super strong ETH
• Data reductions, fixed parameter tractability, and random weighted d-CNF satisfiability

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3581497)