(#022) PCPs and Hardness of Approximation - Aditya Morolia

Date & Time: 30-01-2021, 22:15 IST

Abstract

We all know that a bunch of interesting problems we care about (for example 3-SAT or Graph Coloring) are deemed hard to solve. But what if we relax the definition of solutions and try to approximate them instead? The talk broadly deals with this questions. I'll introduce the concepts of Probabilistically Checkable Proofs, a notion defined to talk about problems of this sort. Then I'll go ahead and formulate the problem of approximating SAT problems in terms of a PCP System. Then I'll state and prove (give an overview) the PCP Theorem, which says that (sigh) approximating this problem is hard. The proof overview is a little involved and will form the bulk of the talk. The proof involves defining the problem in terms of a gap - the fraction of clauses that are not satisfied. Then, use gap amplification and alphabet reduction repeatedly to increase this gap.

Prerequisites

Basic complexity theory (NP Hardness, verifiers) probability theory (Basic definitions), graph theory (Good to have a basic idea of spectral graph theory)

Resources