Random MAX SAT, random MAX CUT, and their phase transitions
From MaRDI portal
Publication:4739584
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
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
This page was built for publication: Random MAX SAT, random MAX CUT, and their phase transitions
