<h2>Probability Theory And Randomized Algorithms</h2>
<ul>
<li><p>Lecture notes from <a href="http://www.cs.cmu.edu/%7Eodonnell/" rel="noreferrer">Ryan O'Donnell</a>'s course <a href="http://www.cs.cmu.edu/%7E15359/" rel="noreferrer">Probability and Computing</a> is pretty neat.</p>
</li>
<li><p>Lecture notes from <a href="http://www.cs.dartmouth.edu/%7Eac" rel="noreferrer">Amit Chakrabarti</a>'s course <a href="http://www.cs.dartmouth.edu/%7Eac/Teach/CS49-Fall11/Notes/lecnotes.pdf" rel="noreferrer">Data Stream Algorithms</a></p>
</li>
</ul>

CC BY-SA 3.0
2012-02-09T16:10:24.520Z
This link is now dead. Could you please fix or it will be removed?
Dave Clarke
CC BY-SA 3.0
2012-02-09T22:12:03.350Z
@Dave, it seems there is no longer a link from Ryan's webpage to the course.  But I don't think removing the entry is a good idea, he might put the link back at some point. Your comment that the link is broken  is sufficient IMO.
Kaveh
CC BY-SA 3.0
2014-07-23T05:30:46.727Z
@DaveClarke  The link is fixed. Yay!
Jardine
CC BY-SA 3.0
2011-01-04T18:01:41.177Z
2014-02-06T02:33:28.563Z
2020-06-17T09:38:08.363Z
Nikhil
<p>A <a href="http://www.cs.princeton.edu/courses/archive/fall02/cs597D/">Theorist's Toolkit</a> by Sanjeev Arora.</p>

<p>I love these notes because it gives you a rather complete set of tools for attacking problems in complexity theory. For example, VC-dimension is used widely for proving lower bounds in the communication model, and these notes explains it so well and from the basics.</p>

CC BY-SA 2.5
2011-01-04T10:03:20.290Z
2011-01-04T10:28:48.777Z
2011-01-04T10:28:48.777Z
Marcos Villagra
<h2><strong>Information Theory</strong></h2>

<ul>
<li><a href="http://www.cs.washington.edu/homes/anuprao/">Anup Rao</a>'s <a href="https://catalyst.uw.edu/workspace/anuprao/15415/86751">Information Theory lecture notes</a> give a detailed description of the cutting-edge tools and how they are applied in recent research, including work from 2010.</li>
</ul>

CC BY-SA 4.0
2024-02-11T18:12:27.307Z
This is not available anymore. Can you share it with me.
Sassy Math
CC BY-SA 2.5
2011-01-04T18:24:42.230Z
2011-01-04T20:39:59.800Z
2011-01-04T20:39:59.800Z
Derrick Stolee
<h2>Discrete math</h2>

<p><a href="http://courses.csail.mit.edu/6.042/fall10/mcs-ftl.pdf">Discrete Mathematics for Computer Science</a> by Lehman, Leighton, and Meyer (<a href="http://www.cs.princeton.edu/courses/archive/fall06/cos341/handouts/mathcs.pdf">older version</a>)</p>

CC BY-SA 3.0
2015-08-01T13:53:59.423Z
Currently more up-to-date version: https://courses.csail.mit.edu/6.042/spring15/mcs.pdf . It feels like finding the right link amid the many outdated mirrors has become an NP-complete problem...
darij grinberg
CC BY-SA 3.0
2016-07-19T22:37:22.370Z
@Jeffε I get a 403 Forbidden error on the first link. The link from the last comment is also password protected. However, this link might help: http://www.seas.harvard.edu/courses/cs20/MIT6_042Notes.pdf.
mehdix
CC BY-SA 3.0
2017-07-20T15:04:49.567Z
Currently up-to-date version: https://courses.csail.mit.edu/6.042/spring17/mcs.pdf . Looks like a pattern has emerged in these links!
darij grinberg
CC BY-SA 2.5
2011-01-12T19:11:35.610Z
I get a 403 Forbidden error on your link.
Derrick Stolee
CC BY-SA 2.5
2011-01-13T01:16:45.723Z
@Derrick: The error is gone or the link is corrected.
Sadeq Dousti
CC BY-SA 2.5
2011-01-13T04:39:00.913Z
Yes, both links work now.....
Derrick Stolee
CC BY-SA 2.5
2011-01-13T07:15:19.257Z
Hence the link to the older version.
Jeffε
CC BY-SA 2.5
2011-01-12T18:21:24.447Z
2011-01-12T18:21:24.447Z
Jeffε
<h2>PCP &amp; Hardness of Approximation</h2>

<ul>
<li>The course offered by <a href="http://www.wisdom.weizmann.ac.il/~feige/pcp.html">Uri Feige</a> is very good.</li>
<li>Another excellent course is offered by <a href="http://www.cs.berkeley.edu/~luca/pcp/">Luca Trevisan</a>.</li>
<li>Yet another course is offered by <a href="http://people.csail.mit.edu/dmoshkov/courses/pcp/index.html">Irit Dinur and Dana Moshkovitz</a>. This one seems more like a link farm, and has few notes.</li>
<li><em>Limits of approximation algorithms : PCPs and Unique Games</em> by <a href="http://www.tcs.tifr.res.in/~prahladh/teaching/2009-10/limits/">Prahladh Harsha</a></li>
</ul>

CC BY-SA 3.0
2015-03-31T15:53:03.140Z
Which of them did you read yourself?
Thomas Ahle
CC BY-SA 2.5
2011-01-08T17:23:39.827Z
2011-01-11T16:39:51.697Z
2011-01-11T16:39:51.697Z
Sadeq Dousti
<h2>Quantum computation and information</h2>

<p>Some excellent lecture notes from this field:</p>

<ul>
<li><a href="http://www.theory.caltech.edu/people/preskill/ph229/#lecture">John Preskill's lecture notes</a> on Quantum Computation. </li>
</ul>

<p>An introductory course on quantum computing. Good enough to be made into a book. I know several researchers who have a printout of these notes on their bookshelf.</p>

<ul>
<li><a href="http://www.cs.uwaterloo.ca/~watrous/quant-info/">John Watrous' lecture notes</a> on the Theory of Quantum Information. </li>
</ul>

<p>An advanced course on quantum information. Some of the best lectures notes I've ever read. </p>

<ul>
<li><a href="http://www.math.uwaterloo.ca/~amchilds/teaching/w08/co781.html">Andrew Childs' lecture notes</a> on Quantum Algorithms. </li>
</ul>

<p>An advanced course on quantum algorithms. A very good resource for recent quantum algorithms. If the original paper on some quantum algorithm is hard to understand, this is where I would check next.</p>

<ul>
<li><a href="http://www.scottaaronson.com/democritus/">Scott Aaronson's lecture notes</a> on Quantum Computing Since Democritus. </li>
</ul>

<p>I can't summarize this course in one line. Read the description on the course web page.</p>

<ul>
<li><a href="http://www.cs.ut.ee/~unruh/qc11/">Unruh's lecture notes</a> on Quantum Cryptography.</li>
</ul>

<p>Includes general introduction to Quantum Computing, as well as crypto-specific topics such as Quantum Key Distribution, Quantum Commitments, Bounded Quantum Storage Model, and Quantum Zero-Knowledge.</p>

CC BY-SA 2.5
2011-01-05T16:38:58.677Z
Very interesting, thanks. I always wanted to learn quantum computing, but didn't have enough time to read a book. Do you know any course devoted to **quantum cryptography**? I found one [here](http://crypto.m2ci.org/teaching/ws10/qcrypto/), but unfortunately, the notes aren't available online.
Sadeq Dousti
CC BY-SA 2.5
2011-01-08T06:02:57.540Z
@Sadeq: Sorry, no idea.
Robin Kothari
CC BY-SA 3.0
2011-01-05T04:47:54.053Z
2012-07-30T23:58:18.743Z
2012-07-30T23:58:18.743Z
Robin Kothari
<h2>Computational Complexity</h2>

<p>There are many excellent courses on this topic. The following is merely the tip of the iceberg. To choose one, I suggest taking a look at the material covered in each course, as well as the level it is offered:</p>

<ul>
<li><a href="http://www.eccc.uni-trier.de/static/books/Introduction_to_Complexity_Theory/" rel="noreferrer">Introduction to Complexity Theory</a> by <strong>Oded Goldreich</strong>. Available in two flavors: <a href="http://www.eccc.uni-trier.de/resources/pdf/cc2.pdf" rel="noreferrer">notes for a two-semester introductory course</a> and <a href="http://www.eccc.uni-trier.de/resources/pdf/notes.pdf" rel="noreferrer">notes for a single-semester course</a>. You can also check Goldreich's <a href="http://www.wisdom.weizmann.ac.il/~oded/cc-book.html" rel="noreferrer">book on computational complexity</a>.</li>
<li>Two different Computational Complexity courses offered at Princeton by <a href="http://www.cs.princeton.edu/courses/archive/spring01/cs522/" rel="noreferrer">Sanjeev Arora</a> and <a href="http://www.cs.princeton.edu/courses/archive/spr06/cos522/" rel="noreferrer">Boaz Barak</a>. You can also check their <a href="http://www.cs.princeton.edu/theory/complexity/" rel="noreferrer">book on computational complexity</a>.</li>
<li><a href="http://www.cs.rutgers.edu/~allender/lecture.notes/" rel="noreferrer">Complexity Theory</a> by <strong>Eric Allender</strong>. Suggested by Boaz Barak at his homepage.</li>
<li><a href="http://www.cs.berkeley.edu/~luca/cs278/" rel="noreferrer">Complexity Theory</a> by <strong>Luca Trevisan</strong>. Suggested by Boaz Barak at his homepage.</li>
<li><a href="http://people.csail.mit.edu/madhu/ST03/" rel="noreferrer">Advanced Complexity Theory</a> by <strong>Madhu Sudan</strong>. Suggested by Boaz Barak at his homepage.</li>
<li><a href="http://pages.cs.wisc.edu/~jyc/710-book.pdf" rel="noreferrer">Lectures in Computational Complexity</a> by <strong>Jin-Yi Cai</strong>. Written more or less in the form of a book.</li>
<li><a href="http://www.cs.toronto.edu/~toni/Courses/PvsNP/CS2429.html" rel="noreferrer">Approaches to the P versus NP Question and Related Complexity Questions</a> by <strong>Toniann Pitassi</strong>, with guest lectures by Steve Cook, Mika Goos, Joshua Grochow, David Liu, and Robert Robere. Graduate course covering many of the state-of-the-art lower bound techniques, several of which aren't well-covered (or covered at all) in other lecture notes.</li>
</ul>

CC BY-SA 3.0
2011-01-08T17:11:01.613Z
2017-01-23T04:51:28.570Z
2017-01-23T04:51:28.570Z
Sadeq Dousti
<h2>Expander Graphs</h2>

<p>The authoritative course is offered by <a href="http://www.math.ias.edu/~boaz/ExpanderCourse/index.html" rel="nofollow noreferrer">Nati Linial and Avi Wigderson</a>. See <a href="https://cstheory.stackexchange.com/q/3586/873">this topic</a> for more information,</p>

CC BY-SA 2.5
2011-01-08T17:30:58.140Z
2011-01-08T17:30:58.140Z
2017-04-13T12:32:28.080Z
Sadeq Dousti
<h2>Computational Geometry</h2>
<p><a href="http://www.cs.umd.edu/class/spring2012/cmsc754/lectures.shtml" rel="noreferrer">Lecture Notes</a> by <a href="http://www.cs.umd.edu/%7Emount/" rel="noreferrer">David Mount</a>.</p>

CC BY-SA 3.0
2011-01-22T23:38:52.633Z
2012-07-31T04:02:35.907Z
2020-06-17T09:38:08.363Z
Vinicius dos Santos
<h2>Combinatorial Optimization</h2>
<ul>
<li>Chandra Chekuri's <em><a href="http://courses.engr.illinois.edu/cs598csc/sp2010/" rel="noreferrer">Topics in Combinatorial Optimization</a></em></li>
<li>Michel Goemans' <em><a href="http://ocw.mit.edu/courses/mathematics/18-997-topics-in-combinatorial-optimization-spring-2004/lecture-notes/" rel="noreferrer">Topics in Combinatorial Optimization</a></em></li>
<li>Lex Schrijver's <em><a href="http://homepages.cwi.nl/%7Elex/files/dict.pdf" rel="noreferrer">A Course in Combinatorial Optimization</a></em></li>
<li>Jan Vondrak's <em><a href="http://theory.stanford.edu/%7Ejvondrak/CS369P.html" rel="noreferrer">Polyhedral techniques in combinatorial optimization</a></em></li>
</ul>

CC BY-SA 3.0
2013-11-01T05:13:03.023Z
And Schrijver: http://homepages.cwi.nl/~lex/files/dict.pdf
Sasho Nikolov
CC BY-SA 3.0
2014-04-05T17:57:16.147Z
Jan Vondrak's notes: http://theory.stanford.edu/~jvondrak/CS369P.html
Chandra Chekuri
CC BY-SA 3.0
2013-11-01T04:50:10.423Z
2014-04-06T04:35:37.133Z
2020-06-17T09:38:08.363Z
Austin Buchanan
<h2>SAT</h2>

<p>I visited a SAT course a few years ago with Professor Welzl. His lecture notes are by far the best I’ve seen throughout my entire studies.</p>

<p>Unfortunately, only the <a href="http://www.inf.ethz.ch/~emo/SmallPieces/SAT.ps">2005 version</a> is online, including a short <a href="http://www.inf.ethz.ch/personal/emo/SmallPieces/SATupdates.html">list of updates</a>.</p>

<p>(The fastest SAT algorithm as well as the constructive proof of the Lovász local lemma come from guys in his group.)</p>

CC BY-SA 2.5
2011-01-04T09:10:54.837Z
2011-01-04T10:05:22.713Z
2011-01-04T10:05:22.713Z
Sacha
<h2>Pseudorandomness</h2>

<p>The best course on the subject is offered by <a href="http://people.seas.harvard.edu/~salil/cs225/" rel="nofollow noreferrer">Salil Vadhan</a>. See also <a href="https://cstheory.stackexchange.com/questions/3540/3557#3557">this topic</a> for a draft of Salil's book on pseudorandomness.</p>

CC BY-SA 2.5
2011-01-08T17:34:06.937Z
2011-01-08T17:34:06.937Z
2017-04-13T12:32:28.080Z
Sadeq Dousti
<h2>Cryptography</h2>

<p>There are a number of excellent lecture notes on the subject, all by famous people in the field. You can choose one (or two) of the following to study; it all depends on your environment, background, and requirements:</p>

<ul>
<li><a href="http://cseweb.ucsd.edu/users/mihir/papers/gb.html" rel="nofollow noreferrer">Lecture Notes on Cryptography</a> by <strong>Shafi Goldwasser</strong> and <strong>Mihir Bellare</strong>, 2008. A series of lectures for <a href="http://web.mit.edu/professional/short-programs/courses/cryptography_computer_security.html" rel="nofollow noreferrer">Cryptography and Computer Security [6.87s]</a>, a one week long course on cryptography taught at the MIT.</li>
<li><a href="http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-876j-advanced-topics-in-cryptography-spring-2003/lecture-notes/" rel="nofollow noreferrer">Advanced Topics in Cryptography</a>, covering more advanced topics than ordinary courses.</li>
<li><a href="http://www.cs.umd.edu/~jkatz/gradcrypto2/scribes.html" rel="nofollow noreferrer">Advanced Topics in Cryptography</a> by <strong>Jonathan Katz</strong>, 2004. Covers an interesting range of topics in advanced cryptography.
A more basic treatment can be found <a href="http://www.cs.umd.edu/~jkatz/TEACHING/crypto_F02/lectures.html" rel="nofollow noreferrer">here</a>.</li>
<li>(Suggested by <a href="https://cstheory.stackexchange.com/users/943/yasser-sobhdel">Yasser</a>): <strong>Yevgeniy Dodis</strong>'s lectures on <a href="http://www.cs.nyu.edu/courses/fall08/G22.3210-001/index.html" rel="nofollow noreferrer">introductory</a> and <a href="http://www.cs.nyu.edu/courses/fall09/G22.3220-001/index.html" rel="nofollow noreferrer">advanced</a> cryptography.</li>
<li><a href="http://www.cs.princeton.edu/courses/archive/spring10/cos433/#NOTES" rel="nofollow noreferrer">Cryptography</a> by <a href="https://cstheory.stackexchange.com/users/1202/boaz-barak">Boaz Barak</a> (2010).</li>
<li><a href="http://u.cs.biu.ac.il/~lindell/89-856/main-89-856.html" rel="nofollow noreferrer">Foundations of cryptography</a> by <strong>Yehuda Lindell</strong>, 2010. Based on <a href="http://www.wisdom.weizmann.ac.il/~oded/foc-book.html" rel="nofollow noreferrer">Goldreich's famous book</a>.</li>
<li><a href="http://www.cs.berkeley.edu/~luca/cs276/#notes" rel="nofollow noreferrer">Cryptography</a> by <strong>Luca Trevisan</strong>. Luca's notes cover the basic topics very nicely.</li>
<li><a href="http://cseweb.ucsd.edu/classes/fa02/cse208/" rel="nofollow noreferrer">Advanced cryptography</a> by <strong>Daniele Micciancio</strong>. Covers lots of advanced topics, and is specially inclined towards <em>secure multi-party protocols</em>.</li>
<li><a href="http://www.courses.fas.harvard.edu/~cs120/lectures/" rel="nofollow noreferrer">Introduction to Cryptography</a> by <strong>Salil Vadhan</strong>. Good for beginner/intermediate level.</li>
</ul>

CC BY-SA 2.5
2011-01-05T04:21:47.833Z
2011-01-08T17:16:58.210Z
2017-04-13T12:32:30.623Z
Sadeq Dousti
<p>The course "Pearls of Algorithms". <a href="http://www.roeglin.org/teaching/WS2010/Pearls.html">Part 3</a>: Probabilistic Analysis and Randomized Algorithms. The <a href="http://www.roeglin.org/teaching/WS2010/Pearls/LectureNotes.pdf">lectures notes</a> are on <a href="http://en.wikipedia.org/wiki/Smoothed_analysis">smoothed analysis</a>. I especially like the figure 1.1 on the third page.</p>

CC BY-SA 2.5
2011-01-21T20:48:53.973Z
2011-01-21T20:48:53.973Z
Oleksandr Bondarenko
<p><strong>Spectral Graph Theory</strong></p>

<ul>
<li><a href="http://www.cs.yale.edu/homes/spielman/561/">Spielman</a> (Yale, 2009)</li>
<li><a href="http://math.ucsd.edu/~jthughes/Math261C/Math261C.html">Chung</a> (UCSD, 2010)</li>
</ul>

CC BY-SA 3.0
2012-04-03T18:14:03.057Z
2012-04-03T18:14:03.057Z
user7545
<p>There has been several questions with the same scheme as this one:</p>

<ul>
<li><a href="https://cstheory.stackexchange.com/q/1168/873">What papers should everyone read</a></li>
<li><a href="https://cstheory.stackexchange.com/q/3253/873">What books should everyone read</a></li>
<li><a href="https://cstheory.stackexchange.com/q/3540/873">What are the recent TCS books whose drafts are available online</a></li>
<li><a href="https://cstheory.stackexchange.com/q/1198/873">what videos should everybody watch</a></li>
</ul>

<p>I was reluctant to post yet another one, but Jeff Erickson's <a href="http://compgeom.cs.uiuc.edu/~jeffe/teaching/algorithms/everything.pdf" rel="noreferrer">lecture notes on algorithms</a> changed my mind. I thought: Oh my! All these years and I haven't seen these excellent notes!</p>

<p>So, I thought there might be other great lecture notes, which are really worth reading. So, for each computer science subfield (<em>data structures, algorithms, theory of computation, computational complexity, cryptography</em>, etc.), recommend the superb lecture notes of your choice, and say <strong>why</strong> you think it excels.</p>

<p>One simple rule to keep it tidy: <strong>One answer per each subfield.</strong> (This will be a community wiki, so you can edit existing answers, and add your recommendation.)</p>

CC BY-SA 2.5
2011-01-04T08:27:32.533Z
You get my vote. If only such a list had existed back when I was a student ...
Anthony Labarre
CC BY-SA 2.5
2011-01-04T09:16:07.423Z
Thank you for the link to Jeff Erickson's excellent notes!
Standa Zivny
CC BY-SA 2.5
2011-01-04T09:41:42.443Z
Should then this question also be community wiki?
Dave Clarke
CC BY-SA 2.5
2011-01-04T10:29:23.190Z
@Dave: Yeah, I've already flagged it as CW. It requires mod attention.
Sadeq Dousti
CC BY-SA 3.0
2013-11-01T11:42:51.740Z
I wish I could upvote this more than once.
Vivek Bagaria
<reference-request><soft-question><big-list>
What Lecture Notes Should Everyone Read?
Sadeq Dousti
# What Lecture Notes Should Everyone Read?

(Asked by: username_0 on 2011-01-04)

There has been several questions with the same scheme as this one:

* [What papers should everyone read](https://cstheory.stackexchange.com/q/1168/873)
* [What books should everyone read](https://cstheory.stackexchange.com/q/3253/873)
* [What are the recent TCS books whose drafts are available online](https://cstheory.stackexchange.com/q/3540/873)
* [what videos should everybody watch](https://cstheory.stackexchange.com/q/1198/873)

I was reluctant to post yet another one, but Jeff Erickson's [lecture notes on algorithms](http://compgeom.cs.uiuc.edu/~jeffe/teaching/algorithms/everything.pdf) changed my mind. I thought: Oh my! All these years and I haven't seen these excellent notes!

So, I thought there might be other great lecture notes, which are really worth reading. So, for each computer science subfield (*data structures, algorithms, theory of computation, computational complexity, cryptography*, etc.), recommend the superb lecture notes of your choice, and say **why** you think it excels.

One simple rule to keep it tidy: **One answer per each subfield.** (This will be a community wiki, so you can edit existing answers, and add your recommendation.)

**Tags:** reference-request, soft-question, big-list

> **Comments:**
> **username_1**: You get my vote. If only such a list had existed back when I was a student ...  
> **username_2**: Thank you for the link to Jeff Erickson's excellent notes!  
> **username_3**: Should then this question also be community wiki?  
> **username_0**: @Dave: Yeah, I've already flagged it as CW. It requires mod attention.  
> **username_4**: I wish I could upvote this more than once.  

---

## 15 answers

### Answer by username_5 on 2011-01-04. Score: 34

## Probability Theory And Randomized Algorithms

* Lecture notes from [Ryan O'Donnell](http://www.cs.cmu.edu/%7Eodonnell/)'s course [Probability and Computing](http://www.cs.cmu.edu/%7E15359/) is pretty neat.
* Lecture notes from [Amit Chakrabarti](http://www.cs.dartmouth.edu/%7Eac)'s course [Data Stream Algorithms](http://www.cs.dartmouth.edu/%7Eac/Teach/CS49-Fall11/Notes/lecnotes.pdf)

> **Comments:**
> **username_3**: This link is now dead. Could you please fix or it will be removed?  
> **username_6**: @Dave, it seems there is no longer a link from Ryan's webpage to the course.  But I don't think removing the entry is a good idea, he might put the link back at some point. Your comment that the link is broken  is sufficient IMO.  
> **username_7**: @DaveClarke  The link is fixed. Yay!  

---

### Answer by username_15 on 2011-01-05. Score: 26

## Quantum computation and information

Some excellent lecture notes from this field:

* [John Preskill's lecture notes](http://www.theory.caltech.edu/people/preskill/ph229/#lecture) on Quantum Computation.

An introductory course on quantum computing. Good enough to be made into a book. I know several researchers who have a printout of these notes on their bookshelf.

* [John Watrous' lecture notes](http://www.cs.uwaterloo.ca/~watrous/quant-info/) on the Theory of Quantum Information.

An advanced course on quantum information. Some of the best lectures notes I've ever read.

* [Andrew Childs' lecture notes](http://www.math.uwaterloo.ca/~amchilds/teaching/w08/co781.html) on Quantum Algorithms.

An advanced course on quantum algorithms. A very good resource for recent quantum algorithms. If the original paper on some quantum algorithm is hard to understand, this is where I would check next.

* [Scott Aaronson's lecture notes](http://www.scottaaronson.com/democritus/) on Quantum Computing Since Democritus.

I can't summarize this course in one line. Read the description on the course web page.

* [Unruh's lecture notes](http://www.cs.ut.ee/~unruh/qc11/) on Quantum Cryptography.

Includes general introduction to Quantum Computing, as well as crypto-specific topics such as Quantum Key Distribution, Quantum Commitments, Bounded Quantum Storage Model, and Quantum Zero-Knowledge.

> **Comments:**
> **username_0**: Very interesting, thanks. I always wanted to learn quantum computing, but didn't have enough time to read a book. Do you know any course devoted to **quantum cryptography**? I found one [here](http://crypto.m2ci.org/teaching/ws10/qcrypto/), but unfortunately, the notes aren't available online.  
> **username_15**: @Sadeq: Sorry, no idea.  

---

### Answer by username_0 on 2011-01-08. Score: 25

## Computational Complexity

There are many excellent courses on this topic. The following is merely the tip of the iceberg. To choose one, I suggest taking a look at the material covered in each course, as well as the level it is offered:

* [Introduction to Complexity Theory](http://www.eccc.uni-trier.de/static/books/Introduction_to_Complexity_Theory/) by **Oded Goldreich**. Available in two flavors: [notes for a two-semester introductory course](http://www.eccc.uni-trier.de/resources/pdf/cc2.pdf) and [notes for a single-semester course](http://www.eccc.uni-trier.de/resources/pdf/notes.pdf). You can also check Goldreich's [book on computational complexity](http://www.wisdom.weizmann.ac.il/~oded/cc-book.html).
* Two different Computational Complexity courses offered at Princeton by [Sanjeev Arora](http://www.cs.princeton.edu/courses/archive/spring01/cs522/) and [Boaz Barak](http://www.cs.princeton.edu/courses/archive/spr06/cos522/). You can also check their [book on computational complexity](http://www.cs.princeton.edu/theory/complexity/).
* [Complexity Theory](http://www.cs.rutgers.edu/~allender/lecture.notes/) by **Eric Allender**. Suggested by Boaz Barak at his homepage.
* [Complexity Theory](http://www.cs.berkeley.edu/~luca/cs278/) by **Luca Trevisan**. Suggested by Boaz Barak at his homepage.
* [Advanced Complexity Theory](http://people.csail.mit.edu/madhu/ST03/) by **Madhu Sudan**. Suggested by Boaz Barak at his homepage.
* [Lectures in Computational Complexity](http://pages.cs.wisc.edu/~jyc/710-book.pdf) by **Jin-Yi Cai**. Written more or less in the form of a book.
* [Approaches to the P versus NP Question and Related Complexity Questions](http://www.cs.toronto.edu/~toni/Courses/PvsNP/CS2429.html) by **Toniann Pitassi**, with guest lectures by Steve Cook, Mika Goos, Joshua Grochow, David Liu, and Robert Robere. Graduate course covering many of the state-of-the-art lower bound techniques, several of which aren't well-covered (or covered at all) in other lecture notes.


---

### Answer by username_8 on 2011-01-04. Score: 23

A [Theorist's Toolkit](http://www.cs.princeton.edu/courses/archive/fall02/cs597D/) by Sanjeev Arora.

I love these notes because it gives you a rather complete set of tools for attacking problems in complexity theory. For example, VC-dimension is used widely for proving lower bounds in the communication model, and these notes explains it so well and from the basics.


---

### Answer by username_9 on 2011-01-04. Score: 21

## **Information Theory**

* [Anup Rao](http://www.cs.washington.edu/homes/anuprao/)'s [Information Theory lecture notes](https://catalyst.uw.edu/workspace/anuprao/15415/86751) give a detailed description of the cutting-edge tools and how they are applied in recent research, including work from 2010.

> **Comments:**
> **username_10**: This is not available anymore. Can you share it with me.  

---

### Answer by username_11 on 2011-01-12. Score: 17

## Discrete math

[Discrete Mathematics for Computer Science](http://courses.csail.mit.edu/6.042/fall10/mcs-ftl.pdf) by Lehman, Leighton, and Meyer ([older version](http://www.cs.princeton.edu/courses/archive/fall06/cos341/handouts/mathcs.pdf))

> **Comments:**
> **username_9**: I get a 403 Forbidden error on your link.  
> **username_0**: @Derrick: The error is gone or the link is corrected.  
> **username_9**: Yes, both links work now.....  
> **username_11**: Hence the link to the older version.  
> **username_12**: Currently more up-to-date version: https://courses.csail.mit.edu/6.042/spring15/mcs.pdf . It feels like finding the right link amid the many outdated mirrors has become an NP-complete problem...  
> **username_13**: @username_11 I get a 403 Forbidden error on the first link. The link from the last comment is also password protected. However, this link might help: http://www.seas.harvard.edu/courses/cs20/MIT6_042Notes.pdf.  
> **username_12**: Currently up-to-date version: https://courses.csail.mit.edu/6.042/spring17/mcs.pdf . Looks like a pattern has emerged in these links!  

---

### Answer by username_0 on 2011-01-08. Score: 17

## PCP & Hardness of Approximation

* The course offered by [Uri Feige](http://www.wisdom.weizmann.ac.il/~feige/pcp.html) is very good.
* Another excellent course is offered by [Luca Trevisan](http://www.cs.berkeley.edu/~luca/pcp/).
* Yet another course is offered by [Irit Dinur and Dana Moshkovitz](http://people.csail.mit.edu/dmoshkov/courses/pcp/index.html). This one seems more like a link farm, and has few notes.
* *Limits of approximation algorithms : PCPs and Unique Games* by [Prahladh Harsha](http://www.tcs.tifr.res.in/~prahladh/teaching/2009-10/limits/)

> **Comments:**
> **username_14**: Which of them did you read yourself?  

---

### Answer by username_0 on 2011-01-08. Score: 15

## Pseudorandomness

The best course on the subject is offered by [Salil Vadhan](http://people.seas.harvard.edu/~salil/cs225/). See also [this topic](https://cstheory.stackexchange.com/questions/3540/3557#3557) for a draft of Salil's book on pseudorandomness.


---

### Answer by username_0 on 2011-01-05. Score: 15

## Cryptography

There are a number of excellent lecture notes on the subject, all by famous people in the field. You can choose one (or two) of the following to study; it all depends on your environment, background, and requirements:

* [Lecture Notes on Cryptography](http://cseweb.ucsd.edu/users/mihir/papers/gb.html) by **Shafi Goldwasser** and **Mihir Bellare**, 2008. A series of lectures for [Cryptography and Computer Security [6.87s]](http://web.mit.edu/professional/short-programs/courses/cryptography_computer_security.html), a one week long course on cryptography taught at the MIT.
* [Advanced Topics in Cryptography](http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-876j-advanced-topics-in-cryptography-spring-2003/lecture-notes/), covering more advanced topics than ordinary courses.
* [Advanced Topics in Cryptography](http://www.cs.umd.edu/~jkatz/gradcrypto2/scribes.html) by **Jonathan Katz**, 2004. Covers an interesting range of topics in advanced cryptography.
  A more basic treatment can be found [here](http://www.cs.umd.edu/~jkatz/TEACHING/crypto_F02/lectures.html).
* (Suggested by [Yasser](https://cstheory.stackexchange.com/users/943/yasser-sobhdel)): **Yevgeniy Dodis**'s lectures on [introductory](http://www.cs.nyu.edu/courses/fall08/G22.3210-001/index.html) and [advanced](http://www.cs.nyu.edu/courses/fall09/G22.3220-001/index.html) cryptography.
* [Cryptography](http://www.cs.princeton.edu/courses/archive/spring10/cos433/#NOTES) by [Boaz Barak](https://cstheory.stackexchange.com/users/1202/boaz-barak) (2010).
* [Foundations of cryptography](http://u.cs.biu.ac.il/~lindell/89-856/main-89-856.html) by **Yehuda Lindell**, 2010. Based on [Goldreich's famous book](http://www.wisdom.weizmann.ac.il/~oded/foc-book.html).
* [Cryptography](http://www.cs.berkeley.edu/~luca/cs276/#notes) by **Luca Trevisan**. Luca's notes cover the basic topics very nicely.
* [Advanced cryptography](http://cseweb.ucsd.edu/classes/fa02/cse208/) by **Daniele Micciancio**. Covers lots of advanced topics, and is specially inclined towards *secure multi-party protocols*.
* [Introduction to Cryptography](http://www.courses.fas.harvard.edu/~cs120/lectures/) by **Salil Vadhan**. Good for beginner/intermediate level.


---

### Answer by username_0 on 2011-01-08. Score: 14

## Expander Graphs

The authoritative course is offered by [Nati Linial and Avi Wigderson](http://www.math.ias.edu/~boaz/ExpanderCourse/index.html). See [this topic](https://cstheory.stackexchange.com/q/3586/873) for more information,


---

### Answer by username_16 on 2011-01-22. Score: 13

## Computational Geometry

[Lecture Notes](http://www.cs.umd.edu/class/spring2012/cmsc754/lectures.shtml) by [David Mount](http://www.cs.umd.edu/%7Emount/).


---

### Answer by username_17 on 2013-11-01. Score: 11

## Combinatorial Optimization

* username_19's *[Topics in Combinatorial Optimization](http://courses.engr.illinois.edu/cs598csc/sp2010/)*
* Michel Goemans' *[Topics in Combinatorial Optimization](http://ocw.mit.edu/courses/mathematics/18-997-topics-in-combinatorial-optimization-spring-2004/lecture-notes/)*
* Lex Schrijver's *[A Course in Combinatorial Optimization](http://homepages.cwi.nl/%7Elex/files/dict.pdf)*
* Jan Vondrak's *[Polyhedral techniques in combinatorial optimization](http://theory.stanford.edu/%7Ejvondrak/CS369P.html)*

> **Comments:**
> **username_18**: And Schrijver: http://homepages.cwi.nl/~lex/files/dict.pdf  
> **username_19**: Jan Vondrak's notes: http://theory.stanford.edu/~jvondrak/CS369P.html  

---

### Answer by username_20 on 2011-01-04. Score: 11

## SAT

I visited a SAT course a few years ago with Professor Welzl. His lecture notes are by far the best I’ve seen throughout my entire studies.

Unfortunately, only the [2005 version](http://www.inf.ethz.ch/~emo/SmallPieces/SAT.ps) is online, including a short [list of updates](http://www.inf.ethz.ch/personal/emo/SmallPieces/SATupdates.html).

(The fastest SAT algorithm as well as the constructive proof of the Lovász local lemma come from guys in his group.)


---

### Answer by username_21 on 2011-01-21. Score: 9

The course "Pearls of Algorithms". [Part 3](http://www.roeglin.org/teaching/WS2010/Pearls.html): Probabilistic Analysis and Randomized Algorithms. The [lectures notes](http://www.roeglin.org/teaching/WS2010/Pearls/LectureNotes.pdf) are on [smoothed analysis](http://en.wikipedia.org/wiki/Smoothed_analysis). I especially like the figure 1.1 on the third page.


---

### Answer by username_22 on 2012-04-03. Score: 9

**Spectral Graph Theory**

* [Spielman](http://www.cs.yale.edu/homes/spielman/561/) (Yale, 2009)
* [Chung](http://math.ucsd.edu/~jthughes/Math261C/Math261C.html) (UCSD, 2010)


---

