{
  "id": "1511.07813",
  "version": "v1",
  "published": "2015-11-24T17:22:25.000Z",
  "updated": "2015-11-24T17:22:25.000Z",
  "title": "2-Xor revisited: satisfiability and probabilities of functions",
  "authors": [
    "Élie de Panafieu",
    "Danièle Gardy",
    "Bernhard Gittenberger",
    "Markus Kuba"
  ],
  "comment": "31 pages, 2 figures",
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "The problem 2-Xor-Sat asks for the probability that a random expression, built as a conjunction of clauses $x \\oplus y$, is satisfiable. We revisit this classical problem by giving an alternative, explicit expression of this probability. We then consider a refinement of it, namely the probability that a random expression computes a specific Boolean function. The answers to both problems involve a description of 2-Xor expressions as multigraphs and use classical methods of analytic combinatorics by expressing probabilities through coefficients of generating functions.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-11-24T17:22:25.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "probability",
      "satisfiability",
      "random expression",
      "specific boolean function",
      "analytic combinatorics"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 31,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv151107813D"
    }
  }
}