Recently I have done an introductory course on complexity theory ( which covered 90% of sipser text book). Now I would like to study the topics Hardness of approximation and PCP's. Can you please suggest me the best available sources (lecture notes or video lectures) to study these topics from the basics.
$\begingroup$
$\endgroup$
1
-
3$\begingroup$ Possible duplicate: What are good references to understanding the proof of the PCP theorem?. $\endgroup$– KavehCommented May 3, 2013 at 18:47
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
I recommend Lectures on Proof Verification and Approximation Algorithms, E.W.Mayr and H.J.Prömel and A.Steger (Eds.), Lecture Notes in Computer Science, vol. 1367, Springer Verlag 1998. These lectures are very suitable for studying these topics from the basic.
$\begingroup$
$\endgroup$
As suggested by Kaveh, the relevant chapters in Arora-Barak are a good starting point.
Soon you'll want to sink your teeth into a significant paper. One difficulty you may encounter is that recent papers in this area build on two decades worth of intense research, which can be intimidating to a beginner. IMHO, the best balance between importance of results and self-containedness of presentation is achieved by Håstad's famous paper "Some Optimal Inapproximability Results" (http://dl.acm.org/citation.cfm?id=502098). I cannot praise the wonderful writing and exposition in that paper enough.
$\begingroup$
$\endgroup$
Here is what we used for our seminars: Theory Reading Group: PCPs and Hardness of Approximation - Fall 2010.
Arora and Barak is a good starting point.
$\begingroup$
$\endgroup$
It's not enough for a self study, but the notes from this DIMACS workshop might help: http://arxiv.org/pdf/1002.3864v1.pdf. Then there is Arora-Barak: http://www.cs.princeton.edu/theory/complexity/ (there is a draft online, and, as it is a draft, it has some typos).
answered May 3, 2013 at 18:12