Recognizing More Unsatisfiable Random k-SAT Instances Efficiently
DOI10.1137/S009753970444096XzbMATH Open1090.05064OpenAlexW2011639573MaRDI QIDQ5470697FDOQ5470697
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
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
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)
Cited In (16)
- On the complexity of random satisfiability problems with planted solutions
- Sherali-adams strikes back
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- Short propositional refutations for dense random 3CNF formulas
- Title not available (Why is that?)
- 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
- Some Results on Random Unsatisfiable k-Sat Instances and Approximation Algorithms Applied to Random Structures
- Approximation algorithms for discrete polynomial optimization
- Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT
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)
