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

Official source

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.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related concepts

No results

Related people

Related courses

Related publications

No results

No results

No results

Related units

Related lectures

No results

No results