{
  "id": "math/0306047",
  "version": "v2",
  "published": "2003-06-02T21:03:14.000Z",
  "updated": "2003-06-13T19:00:03.000Z",
  "title": "Random MAX SAT, Random MAX CUT, and Their Phase Transitions",
  "authors": [
    "Don Coppersmith",
    "David Gamarnik",
    "Mohammad Hajiaghayi",
    "Gregory B. Sorkin"
  ],
  "comment": "49 pages",
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "Given a 2-SAT formula $F$ consisting of $n$ variables and $\\cn$ random clauses, what is the largest number of clauses $\\max F$ satisfiable by a single assignment of the variables? We bound the answer away from the trivial bounds of $(3/4)cn$ and $cn$. We prove that for $c<1$, the expected number of clauses satisfiable is $\\cn-\\Theta(1/n)$; for large $c$, it is $((3/4)c + \\Theta(\\sqrt{c}))n$; for $c = 1+\\eps$, it is at least $(1+\\eps-O(\\eps^3))n$ and at most $(1+\\eps-\\Omega(\\eps^3/\\ln \\eps))n$; and in the ``scaling window'' $c= 1+\\Theta(n^{-1/3})$, it is $cn-\\Theta(1)$. In particular, just as the decision problem undergoes a phase transition, our optimization problem also undergoes a phase transition at the same critical value $c=1$. Nearly all of our results are established without reference to the analogous propositions for decision 2-SAT, and as a byproduct we reproduce many of those results, including much of what is known about the 2-SAT scaling window. We consider ``online'' versions of MAX-2-SAT, and show that for one version, the obvious greedy algorithm is optimal. We can extend only our simplest MAX-2-SAT results to MAX-k-SAT, but we conjecture a ``MAX-k-SAT limiting function conjecture'' analogous to the folklore satisfiability threshold conjecture, but open even for $k=2$. Neither conjecture immediately implies the other, but it is natural to further conjecture a connection between them. Finally, for random MAXCUT (the size of a maximum cut in a sparse random graph) we prove analogous results.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2003-06-13T19:00:03.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60C05",
      "60J85",
      "82B26",
      "05C80",
      "05C90"
    ],
    "keywords": [
      "phase transition",
      "random max sat",
      "random max cut",
      "folklore satisfiability threshold conjecture",
      "decision problem undergoes"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 49,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2003math......6047C"
    }
  }
}