Recognizing More Unsatisfiable Random k-SAT Instances Efficiently

DOI10.1137/S009753970444096XMaRDI QIDQ5470697zbMATH OpenOpenAlexFDO

Authors Joel Friedman, Michael Krivelevich, Andreas Goerdt

Publication date 1 June 2006

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

Full work available at URL https://doi.org/10.1137/s009753970444096x

zbMATH Keywords

spectral methodsrandom structuresrandom satisfiability

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorics in computer science (68R05) Classical propositional logic (03B05) Eigenvalues, estimation of eigenvalues, upper and lower bounds of ordinary differential operators (34L15) Asymptotic distribution of eigenvalues, asymptotic theory of eigenfunctions for ordinary differential operators (34L20)

Recommendations

• scientific article; zbMATH DE number 1754601
• Recognizing more random unsatisfiable 3-SAT instances efficiently
• scientific article; zbMATH DE number 1689045
• An efficient approach to solving random \(k\)-SAT problems
• Some Results on Random Unsatisfiable k-Sat Instances and Approximation Algorithms Applied to Random Structures
• scientific article; zbMATH DE number 1929945
• Improving configuration checking for satisfiable random \(k\)-SAT instances
• Computing unsatisfiable \(k\)-SAT instances with few occurrences per variable
• A Better Algorithm for Random k-SAT
• A better algorithm for random \(k\)-SAT

Cited in

(16)

• On the complexity of random satisfiability problems with planted solutions
• Sherali-adams strikes back
• scientific article; zbMATH DE number 1754601 (Why is no real title available?)
• An efficient approach to solving random \(k\)-SAT problems
• Can rare SAT formulae be easily recognized? On the efficiency of message-passing algorithms forK-SAT at large clause-to-variable ratios
• Noisy tensor completion via the sum-of-squares hierarchy
• scientific article; zbMATH DE number 1689045 (Why is no real title available?)
• Short propositional refutations for dense random 3CNF formulas
• Certifying unsatisfiability of random \(2k\)-SAT formulas using approximation techniques.
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Recognizing more random unsatisfiable 3-SAT instances efficiently
• Approximating independent set in perturbed graphs
• Approximation algorithms for discrete polynomial optimization
• Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT
• Some Results on Random Unsatisfiable k-Sat Instances and Approximation Algorithms Applied to Random Structures
• Sherali-Adams strikes back

This page was built for publication: Recognizing More Unsatisfiable Random k-SAT Instances Efficiently

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