Random MAX SAT, random MAX CUT, and their phase transitions

DOI10.1002/rsa.20015zbMath1077.68118arXivmath/0306047OpenAlexW2804968020MaRDI QIDQ4739584

Gregory B. Sorkin, David Gamarnik, Don Coppersmith, Mohammad Taghi Hajiaghayi

Publication date: 6 August 2004

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0306047

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Related Items (25)

On the maximal cut in a random hypergraph ⋮ Kolmogorov complexity based upper bounds for the unsatisfiability threshold of random k-SAT ⋮ Lower and Upper Bounds for Random Mimimum Satisfiability Problem ⋮ PHASE TRANSITIONS OF EXPSPACE-COMPLETE PROBLEMS: A FURTHER STEP ⋮ A novel algorithm for Max Sat calling MOCE to order ⋮ Disorder chaos in some diluted spin Glass models ⋮ MAX CUT in weighted random intersection graphs and discrepancy of sparse random set systems ⋮ The number of satisfying assignments of random 2‐SAT formulas ⋮ An upper (lower) bound for Max (Min) CSP ⋮ Exact enumeration of satisfiable 2-SAT formulae ⋮ CHAMP: a multipass algorithm for Max Sat based on saver variables ⋮ A tighter upper bound for random MAX \(2\)-SAT ⋮ Go-MOCE: greedy order method of conditional expectations for Max Sat ⋮ The Satisfiability Threshold fork-XORSAT ⋮ Local Limit Theorems for the Giant Component of Random Hypergraphs ⋮ Phase transitions of contingent planning problem ⋮ Phase Transition for Maximum Not-All-Equal Satisfiability ⋮ Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT ⋮ On the satisfiability threshold of formulas with three literals per clause ⋮ Combinatorial approach to the interpolation method and scaling limits in sparse random graphs ⋮ Sparse graphs: Metrics and random models ⋮ PHASE TRANSITIONS OF EXPSPACE-COMPLETE PROBLEMS ⋮ Using the method of conditional expectations to supply an improved starting point for CCLS ⋮ Unnamed Item ⋮ The Ising Antiferromagnet and Max Cut on Random Regular Graphs

Cites Work

• The 3-XORSAT threshold.
• The threshold for random k-SAT is 2 ^k (ln 2 - O(k))
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Random MAX SAT, random MAX CUT, and their phase transitions