{
  "id": "enwiki-001116509283",
  "slug": "averaging-argument",
  "title": "Averaging argument",
  "qid": "",
  "lead": "In computational complexity theory and cryptography, averaging argument is a standard argument for proving theorems. It usually allows us to convert probabilistic polynomial-time algorithms into non-uniform polynomial-size circuits.",
  "body": "In computational complexity theory and cryptography, averaging argument is a standard argument for proving theorems. It usually allows us to convert probabilistic polynomial-time algorithms into non-uniform polynomial-size circuits. Proof: Suppose there are N people and B books. Each person likes at least B/3 of the books. Let people leave a mark on the book they like. Then, there will be at least M=(NB)/3 marks. The averaging argument claims that there exists a book with at least N/3 marks on it. Assume, to the contradiction, that no such book exists. Then, every book has fewer than N/3 marks. However, since there are B books, the total number of marks will be fewer than (NB)/3 , contradicting the fact that there are at least M marks. \\scriptstyle\\blacksquare Let f be some function. The averaging argument is the following claim: if we have a circuit C such that C(x, y) = f(x) with probability at least \\rho , where x is chosen at random and y is chosen independently from some distribution Y over \\{0, 1\\}^m (which might not even be efficiently sampleable) then there exists a single string y_0 \\in \\{0, 1\\}^m such that \\Pr_x[C(x, y_0) = f(x)] \\ge \\rho . Indeed, for every y define p_y to be \\Pr_x[C(x, y) = f(x)] then \\Pr_{x,y}[C(x, y) = f(x)] = E_y[p_y] \\, and then this reduces to the claim that for every random variable Z , if E[Z] \\ge \\rho then \\Pr[Z \\ge \\rho] > 0 (this holds since E[Z] is the weighted average of Z and clearly if the average of some values is at least \\rho then one of the values must be at least \\rho ).",
  "categories": [
    "22964558",
    "29176222",
    "29176587",
    "32409276"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1116509283",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1665955286.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001116509283",
    "type": "webpage",
    "title": "Averaging argument",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/averaging-argument",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          17
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          17
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001116509283",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1116509283",
    "note": "Immutable snapshot enwiki-001116509283"
  }
}