<p>As suggested by Kaveh, the relevant chapters in Arora-Barak are a good starting point.</p>

<p>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 <em>intense</em> 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" (<a href="http://dl.acm.org/citation.cfm?id=502098">http://dl.acm.org/citation.cfm?id=502098</a>). I cannot praise the wonderful writing and exposition in that paper enough.</p>

CC BY-SA 3.0
2013-05-08T03:25:23.030Z
2013-05-08T03:25:23.030Z
chax
<p>I recommend <em>Lectures on Proof Verification and Approximation Algorithms</em>,  E.W.Mayr and H.J.Prömel and A.Steger (Eds.), <a href="http://link.springer.com/book/10.1007/BFb0053010/page/1">Lecture Notes in Computer Science, vol. 1367</a>, Springer Verlag 1998. These lectures are very suitable for studying these topics from the basic.</p>

CC BY-SA 3.0
2013-05-03T17:42:43.033Z
2013-05-03T18:05:56.367Z
2013-05-03T18:05:56.367Z
vb le
<p>Here is what we used for our seminars: <a href="http://www.cs.toronto.edu/theory/PCPReadingGroup.html" rel="nofollow">Theory Reading Group: PCPs and Hardness of Approximation - Fall 2010</a>.</p>

<p>Arora and Barak is a good starting point.</p>

CC BY-SA 3.0
2013-05-03T18:42:09.757Z
2013-05-03T18:42:09.757Z
Kaveh
<p>It's not enough for a self study, but the notes from this DIMACS workshop might help: <a href="http://arxiv.org/pdf/1002.3864v1.pdf" rel="nofollow">http://arxiv.org/pdf/1002.3864v1.pdf</a>. Then there is Arora-Barak: <a href="http://www.cs.princeton.edu/theory/complexity/" rel="nofollow">http://www.cs.princeton.edu/theory/complexity/</a> (there is a draft online, and, as it is a draft, it has some typos). </p>

CC BY-SA 3.0
2013-05-03T18:12:38.660Z
2013-05-03T23:46:08.257Z
2013-05-03T23:46:08.257Z
Sasho Nikolov
<p>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. </p>

CC BY-SA 3.0
2013-05-03T18:47:20.603Z
Possible duplicate: [What are good references to understanding the proof of the PCP theorem?](http://cstheory.stackexchange.com/questions/45/what-are-good-references-to-understanding-the-proof-of-the-pcp-theorem).
Kaveh
<cc.complexity-theory><approximation-hardness><pcp>
How to start studying topics Hardness of approximation and PCP's
Kumar
# How to start studying topics Hardness of approximation and PCP's

(Asked by: username_0 on 2013-05-03)

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.

**Tags:** cc.complexity-theory, approximation-hardness, pcp

> **Comments:**
> **username_1**: Possible duplicate: [What are good references to understanding the proof of the PCP theorem?](http://cstheory.stackexchange.com/questions/45/what-are-good-references-to-understanding-the-proof-of-the-pcp-theorem).  

---

## 4 answers

### Answer by username_2 on 2013-05-08. Score: 7

As suggested by username_1, 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.


---

### Answer by username_3 on 2013-05-03. Score: 7

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](http://link.springer.com/book/10.1007/BFb0053010/page/1), Springer Verlag 1998. These lectures are very suitable for studying these topics from the basic.


---

### Answer by username_1 on 2013-05-03. Score: 2

Here is what we used for our seminars: [Theory Reading Group: PCPs and Hardness of Approximation - Fall 2010](http://www.cs.toronto.edu/theory/PCPReadingGroup.html).

Arora and Barak is a good starting point.


---

### Answer by username_4 on 2013-05-03. Score: 2

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).


---

