A Better Algorithm for Random k-SAT

DOI10.1007/978-3-642-02927-1_25MaRDI QIDQ3638042zbMATH OpenOpenAlexFDO

Authors Amin Coja-Oghlan

Publication date 14 July 2009

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02927-1_25

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• A better algorithm for random \(k\)-SAT
• Analyzing Walksat on random formulas
• Analyzing Walksat on random formulas
• Theory and Applications of Satisfiability Testing
• Why almost all satisfiable k-CNF formulas are easy

Cited in

(27)

• A combinatorial analysis for the critical clause tree
• Proof of the satisfiability conjecture for large \(k\)
• Time complexity analysis of evolutionary algorithms on random satisfiable k-CNF formulas
• An algorithm for random signed 3-SAT with intervals
• Analyzing Walksat on random formulas
• Counting good truth assignments of random k-SAT formulae
• Cryptographic hardness of random local functions. Survey
• Strong Refutation Heuristics for Random k-SAT
• Pushing Random Walk Beyond Golden Ratio
• An improved exponential-time algorithm for k -SAT
• On the random satisfiable process
• Why almost all satisfiable k-CNF formulas are easy
• scientific article; zbMATH DE number 1738648 (Why is no real title available?)
• Decoding from pooled data: sharp information-theoretic bounds
• Counting solutions to random CNF formulas
• Analyzing Walksat on random formulas
• Theory and Applications of Satisfiability Testing
• Theory and Applications of Satisfiability Testing
• Theory and Applications of Satisfiability Testing
• Beating the random assignment on constraint satisfaction problems of bounded degree
• On belief propagation guided decimation for random k-SAT
• A better algorithm for random \(k\)-SAT
• On an online random k‐SAT model
• Recognizing More Unsatisfiable Random k-SAT Instances Efficiently
• Locally satisfiable formulas
• A randomized algorithm for 3-SAT
• An efficient approach to solving random \(k\)-SAT problems

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

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