Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2k-SAT

DOI10.1016/J.TCS.2004.07.017zbMATH Open1086.68143OpenAlexW2040072977MaRDI QIDQ706614FDOQ706614

Authors: Amin Coja-Oghlan, Andreas Goerdt, André Lanka, Frank Schädlich 

Publication date: 9 February 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.07.017

Recommendations

• Certifying unsatisfiability of random \(2k\)-SAT formulas using approximation techniques.
• scientific article; zbMATH DE number 1929945
• Some Results on Random Unsatisfiable k-Sat Instances and Approximation Algorithms Applied to Random Structures
• Recognizing More Unsatisfiable Random k-SAT Instances Efficiently
• A better algorithm for random \(k\)-SAT

zbMATH Keywords

Hypergraph discrepancyProbabilistic analysisRandom \(k\)-SATRandom MAX \(2\)-SAT

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Cites Work

• Title not available (Why is that?)
• The eigenvalues of random symmetric matrices
• Relations between average case complexity and approximation complexity
• Title not available (Why is that?)
• Geometric algorithms and combinatorial optimization
• Some optimal inapproximability results
• Title not available (Why is that?)
• Title not available (Why is that?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• The Largest Eigenvalue of Sparse Random Graphs
• Approximating the unsatisfiability threshold of random formulas
• Sharp thresholds of graph properties, and the $k$-sat problem
• Title not available (Why is that?)
• Spectral techniques applied to sparse random graphs
• Title not available (Why is that?)
• Approximating the independence number and the chromatic number in expected polynomial time
• Exact and approximative algorithms for coloring G(n,p)
• Title not available (Why is that?)
• Selecting Complementary Pairs of Literals
• A polylogarithmic approximation of the minimum bisection
• A threshold for unsatisfiability
• Random MAX SAT, random MAX CUT, and their phase transitions
• The threshold for random k-SAT is 2 ^k (ln 2 - O(k))
• Title not available (Why is that?)
• Recognizing more random unsatisfiable 3-SAT instances efficiently
• Title not available (Why is that?)
• Some Results on Random Unsatisfiable k-Sat Instances and Approximation Algorithms Applied to Random Structures
• Title not available (Why is that?)
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• The Lovász number of random graphs

Cited In (8)

• On the complexity of random satisfiability problems with planted solutions
• A Spectral Method for MAX2SAT in the Planted Solution Model
• Title not available (Why is that?)
• Approximating highly satisfiable random 2-SAT
• Title not available (Why is that?)
• Certifying unsatisfiability of random \(2k\)-SAT formulas using approximation techniques.
• Message passing algorithms for MLS-3LIN problem
• Algorithms and Computation

This page was built for publication: Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT

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