Recognizing More Unsatisfiable Random k-SAT Instances Efficiently
From MaRDI portal
Publication:5470697
Classical propositional logic (03B05) Random graphs (graph-theoretic aspects) (05C80) 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) Combinatorics in computer science (68R05)
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
(17)- Noisy tensor completion via the sum-of-squares hierarchy
- Approximating independent set in perturbed graphs
- scientific article; zbMATH DE number 1689045 (Why is no real title available?)
- Can rare SAT formulae be easily recognized? On the efficiency of message-passing algorithms forK-SAT at large clause-to-variable ratios
- Recognizing more random unsatisfiable 3-SAT instances efficiently
- Approximation algorithms for discrete polynomial optimization
- Some Results on Random Unsatisfiable k-Sat Instances and Approximation Algorithms Applied to Random Structures
- scientific article; zbMATH DE number 1754601 (Why is no real title available?)
- On the complexity of random satisfiability problems with planted solutions
- Sherali-adams strikes back
- Sherali-Adams strikes back
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Certifying unsatisfiability of random 2k-SAT formulas using approximation techniques.
- Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT
- On the satisfiability of random 3-SAT formulas with \(k\)-wise independent clauses
- Short propositional refutations for dense random 3CNF formulas
- An efficient approach to solving random \(k\)-SAT problems
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)
