Office: TAY 3.134
Office Hours: WF 2:30-3:30, or by appointment.
Office (for office hours): ENS 31NQ Desk #1
Office (for all other purposes): TAY 3.108
Office Hours: M 2-3
2005 version of course
N. Alon and J. H. Spencer, "The Probabilistic Method" ( ebook available with UT EID)
L. Babai and P. Frankl, "Linear Algebra Methods in Combinatorics, with applications to geometry and computer science"
For students wishing to review probability, I recommend the first two chapters (except Section 2.6) of
R. Meester, A Natural Introduction to Probability Theory.
For general problem-solving and proof techniques, I recommend Chapters 2 and 3 of
P. Zeitz, The Art and Craft of Problem Solving,
and for basic counting I recommend Sections 6.1 and 6.2 of the same book.
Manuel Blum's lecture notes contain a counting argument showing the existence of hard functions.
Linear algebra reference.
Madhu Sudan's lecture notes on coding theory.
My Pseudorandomness lecture notes include three lectures on coding theory.
My talk on codes in theoretical computer science.
Nisan-Wigderson Pseudorandom Generator
Hoory-Linial-Wigderson survey of expander graphs
Lecture notes on expander graphs and random walks on expanders from my Pseudorandomness class.
Lecture notes on extractors and their applications from my Pseudorandomness class.
For more on extractors, see Nisan's survey and Shaltiel's survey.
My paper giving a simple extractor construction, and an application to inapproximability.
Problem Set #1
Problem Set #2 Solutions
Problem Set #3 Solutions
Problem Set #4 Solutions
Problem Set #5 Solutions
Problem Set #6 Solutions
Problem Set #7 Solutions
Problem Set #8 Solutions
The final exam will be cumulative and held on Monday, December 17 from 9am-noon in ENS 109. No make-up exams will be given, so plan accordingly. For the midterm, you may bring a single, 8.5x11 inch, handwritten sheet of paper (you may use both sides); for the final you may bring two such sheets. No calculators are allowed (they won't be necessary).