Recognizing More Unsatisfiable Random k-SAT Instances Efficiently

DOI10.1137/S009753970444096XzbMath1090.05064OpenAlexW2011639573MaRDI QIDQ5470697

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) Asymptotic distribution of eigenvalues, asymptotic theory of eigenfunctions for ordinary differential operators (34L20) Classical propositional logic (03B05) Eigenvalues, estimation of eigenvalues, upper and lower bounds of ordinary differential operators (34L15)

Related Items (7)

On the Complexity of Random Satisfiability Problems with Planted Solutions ⋮ Noisy tensor completion via the sum-of-squares hierarchy ⋮ Approximation algorithms for discrete polynomial optimization ⋮ Approximating independent set in perturbed graphs ⋮ Short propositional refutations for dense random 3CNF formulas ⋮ Sherali-adams strikes back ⋮ Unnamed Item

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