Students should consult this page at least once a week for important information.
Lectures: Thursday 10-12 SF 3202
Instructor: Toniann Pitassi, email: toni@cs
Office: Sandford Fleming 2305A, 978-3695
Office Hours: by appointment (send an email message).
Text: There is no required text for this course. Background material on computational complexity can be found in the book Introduction to the Theory of Computation by Michael Sipser.
Course Information Sheet
Problem Set 1
Problem Set 2
Sudan, Trevisan, Vadhan
Trevisan's extractor paper
Journal version of Luca's paper
Pre-Trevisan survey on extractors
Raz, Resolution lower bounds for WPHP
Beame-Pitassi, lower bounds for PHP