• Calendar

December 30, Monday
11:00 – 13:00

Many classical problems (e.g. Vertex-Cover, Maximum Clique) cannot be efficiently computed unless P=NP. Thus, the next best thing would be to find an approximate solution guaranteed to be "close" to the optimum. The search for such approximation algorithms has had, in many cases, limited success. In the early 90s, an important breakthrough was achieved with the discovery of the PCP (Probabilistically Checkable Proofs) theorem. This deep theorem enabled, for the first time, proving that certain problems cannot be approximated better than a certain factor, unless P=NP. In the past decade various improvements of the PCP theorem were discovered, along with highly non-trivial ways of using it to obtain stronger (sometimes even tight) hardness of approximation results. In this talk I will give an overview of the PCP theorem and its basic connection to hardness of approximation. I will outline a central paradigm by which many of the stronger PCP hardness of approximation results have been obtained. I will introduce the "long-code" - a combinatorial object that plays a central role in these constructions, focusing in particular on vertex-cover, and hypergraph-coloring. Finally, I will touch on some of the beautiful mathematical techniques that are relied on for these constructions, including Erdos-Ko-Rado theorems on intersecting families of finite sets, influence of variables on Boolean functions, and the chromatic number of the Kneser graph. I will try to demonstrate how these seemingly unrelated objects are all really disguises of the "long-code".