This is one of the courses I took up in my 5th semester of my BSc. This was taken by Arvind and we covered quite a lot of "cutting-edge" stuff in it.
There was a first round of scribing that we did, I think we covered roughly 7 lectures in that. Then we covered more on error correcting codes and went into extractors.
The lectures on expanders that followed after a while excited me and I decided to scribe them myself, and also the following lectures on the PCP theorems.
There was a first round of scribing that we did, I think we covered roughly 7 lectures in that. Then we covered more on error correcting codes and went into extractors.
The lectures on expanders that followed after a while excited me and I decided to scribe them myself, and also the following lectures on the PCP theorems.
We then had a lecture on Expander Codes, and then discussed Razbarov's lower bounds on monotone circuits for clique. In the final class we discussed depth lowerbounds for monotone circuits evaluating matching.
You would need complexity.sty for some of the source files.
Lectures on Pseudorandom Generators:
- Lecture 1 and 2: [TeX][PDF]
- Lectures 3 and part of 4: [TeX][PDF]
- Lectures 4(rest of it) and 5:[TeX][PDF]
- Lecture 6: [TeX][PDF]
- Lecture 7: [TeX][PDF
Lectures on Error Correcting Codes and Extractors: (haven't been TeX-ed yet)
Lecture notes on Expander Graphs: [TeX][PDF]
Lecture notes on the PCP Theorem:[TeX][PDF]
Lecture on Expander Codes: [TeX][PDF]
Lecture on Monotone Circuit Lower Bounds for Clique: [TeX][PDF]
Lecture on lower bounds for monotone circuits for matching: (haven't been TeX-ed yet)
Final Examination: [PDF]
Lecture notes on Expander Graphs: [TeX][PDF]
Lecture notes on the PCP Theorem:[TeX][PDF]
Lecture on Expander Codes: [TeX][PDF]
Lecture on Monotone Circuit Lower Bounds for Clique: [TeX][PDF]
Lecture on lower bounds for monotone circuits for matching: (haven't been TeX-ed yet)
Final Examination: [PDF]
No comments:
Post a Comment