Averaging argument

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

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 ).

Text derived from https://en.wikipedia.org/w/index.php?oldid=1116509283 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001116509283 · captured 1665955286.0 · version history

Cite this page as: encyclopegia.org, “Averaging argument”, snapshot enwiki-001116509283. https://encyclopegia.org/a/averaging-argument

Sources cited in this revision

Extracted from the cited revision's reference blocks; absent citations are not invented.