Notes on the PCP Theorem and the Hardness of Approximation: Part 1

In this note, we are going to state the PCP theorem and its relation to the hardness of approximating some NP-hard problem.

PCP Theorem: the Interactive Proof View

Intuitively, a PCP (Probabilistically Checkable Proof) system is an interactive proof system where the verifier is given r(n) random bits and he is allowed to look into the proof \pi in q(n) many locations. If the string x \in \{0,1\}^n is indeed in the language, then there exists a proof so that the verifier always accepts. However, if x is not in the language, no prover can convince this verier with probability more than 1/2. The proof has to be short i.e., of size at most q(n) 2^{r(n)}. This class of language is designated as PCP[r(n), q(n)].

Theorem A (PCP theorem). Every NP language has a highly efficient PCP verifier. In particular,

NP = PCP[O(\log n), O(1)].

Continue reading “Notes on the PCP Theorem and the Hardness of Approximation: Part 1”

Advertisements

Impagliazzo’s Hardcore Lemma: a Proof

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.

Continue reading “Impagliazzo’s Hardcore Lemma: a Proof”