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

DOI10.1016/j.tcs.2004.07.017zbMath1086.68143OpenAlexW2040072977MaRDI QIDQ706614

Andreas Goerdt, André Lanka, Amin Coja-Oghlan, 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

zbMATH Keywords

Probabilistic analysisHypergraph discrepancyRandom \(k\)-SATRandom MAX \(2\)-SAT

Mathematics Subject Classification ID

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

Related Items

On the Complexity of Random Satisfiability Problems with Planted Solutions ⋮ Message passing algorithms for MLS-3LIN problem ⋮ A Spectral Method for MAX2SAT in the Planted Solution Model

Cites Work

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