Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Averaging argument
Summary
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.
Example: If every person likes at least 1/3 of the books in a library, then the library has a book, which at least 1/3 of people like.
Proof: Suppose there are people and books. Each person likes at least of the books. Let people leave a mark on the book they like. Then, there will be at least marks. The averaging argument claims that there exists a book with at least marks on it. Assume, to the contradiction, that no such book exists. Then, every book has fewer than marks. However, since there are books, the total number of marks will be fewer than , contradicting the fact that there are at least marks.
Let X and Y be sets, let p be a predicate on X × Y and let f be a real number in the interval [0, 1]. If for each x in X and at least f |Y| of the elements y in Y satisfy p(x, y), then there exists a y in Y such that there exist at least f |X| elements x in X that satisfy p(x, y).
There is another definition, defined using the terminology of probability theory.
Let be some function. The averaging argument is the following claim: if we have a circuit such that with probability at least , where is chosen at random and is chosen independently from some distribution over (which might not even be efficiently sampleable) then there exists a single string such that .
Indeed, for every define to be then
and then this reduces to the claim that for every random variable , if then (this holds since is the weighted average of and clearly if the average of some values is at least then one of the values must be at least ).
This argument has wide use in complexity theory (e.g. proving ) and cryptography (e.g. proving that indistinguishable encryption results in semantic security). A plethora of such applications can be found in Goldreich's books.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.