You are currently browsing the tag archive for the ‘von Neumann’ tag.

# Tag Archive

## Impagliazzo’s Hardcore Lemma: a Proof

September 20, 2016 in Computer Science, Expository, Game Theory, Mathematics, Theoretical Computer Science, Uncategorized | Tags: Arora-Barak, Game Theroy, Hardcore Lemma, Hardness Amplification, Impagliazzo, Minimax Theorem, von Neumann | Leave a comment

Informally speaking, Impagliazzo’s hardcore lemma says that if a boolean function is “hard to compute on average” by small circuits, then there exists a set of inputs on which the same function is “extremely hard to compute on average” by slightly smaller circuits.

In this post, I am going to explain how I understand the proof of the hardcore lemma presented in the Arora-Barak complexity book (here). Because the formal proof can be found in the book I intend to write in an informal way. I think some subtleties are involved in turning the context of the lemma into a suitable two-player zero-sum game. Doing so enables one to use von Neumann’s minimax theorem to effectively “exchange the quantifiers” in the contrapositive statement of the lemma. Although the Arora-Barak proof mentions these subtleties, I am going to explore these in more detail and in a more accessible way for a beginner like me.