CS388C: Combinatorics and Graph Theory (Spring 2014)

Syllabus: Syllabus.
Logistics: TTh 2:00 - 3:30
GDC 2.210
Unique Number: 54000
Course web page: http://www.cs.utexas.edu/~diz/388C
Professor: David Zuckerman
Email: diz@cs.utexas.edu
Office: GDC 4.508
Phone: 471-9729
Office Hours: W 2:15-3:45.
TA: Abhishek Bhowmick
Email: bhowmick[AT]cs[DOT]utexas[DOT]edu
Office (for office hours): GDC 1.302, Desk 1
Office (for all other purposes): GDC 4.504B
Office Hours: MF 10:00-10:45.
Useful References: Balls in bins: twelvefold way
Scribe notes containing Shannon's counting argument for the existence of functions with large circuit complexity
V. Guruswami, A. Rudra, and M. Sudan, Essential Coding Theory, a book draft.
S. Hoory, N. Linial, and A. Wigderson, Expander Graphs and Their Applications, a survey.
Lecture notes from my class includes pseudorandomness, codes, expanders, and more.
Slides for lecture on randomness extractors.
Ronen Shaltiel, An introduction to randomness extractors
Salil Vadhan's monograph on pseudorandomness contains chapters on expander graphs and randomness extractors.
The theorem about AB+C increasing the entropy rate is from Section 8.2 of this paper of mine.
Zeev Dvir's Incidence Theorems and Applications includes the Sylvester-Gallai theorem in Section 5.1.
Problem Sets: Problem Set #1
Future problem sets posted on Canvas.
Canvas: We will use Canvas, which contains Piazza. Homeworks and grades will be posted on Canvas. We will use Piazza for class discussion. Instead of emailing questions to the teaching staff, please post your question to Piazza.

Last modified: April 30, 2014