CMSC 652, Complexity Theory, Fall 2009, MW
Office: AVW 3263, Phone: 301-405-2695
Instructor's office Hours: Mon 3-5 pm and Fri 12-1 pm in AVW
Course Time and Location: MW 12:30-1:45 PM, CMSC 3120
No required textbook, but Arora-Barak is recommended.
Announcements and Links:
- The Complexity Zoo
- Check out Timothy Gowers'
discussion of complexity lower-bounds
- Lance Fortnow's blog post on the history of IP = PSPACE
- For part of the class (20-30 min.s) on Oct. 7,
student Peter Fontana
gave a guest lecture on time-space tradeoffs for SAT; see the
slides that he used for a longer presentation.
- For part of the class (about 20 min.s) on Dec. 9,
student Rong Zhou gave a guest lecture on the foundations of quantum
mechanics, and the connections to quantum computing.
The following is an approximate schedule:
- introduction; basic time- and space-complexity classes and
relations among them (eight lectures: Aug 31 - Sep 28);
- the polynomial hierarchy (Sep 30, Oct 5), alternation and time-space
tradeoffs for SAT (Oct 7),
non-uniform and uniform complexity, theorems of Karp-Lipton and Kannan
- randomized computation, pseudorandomness, and randomness-extraction
(Oct 19-Nov 2);
- interactive proofs, including AM, IP=PSPACE, program-checking, and
MIP; quick coverage of k-wise independence (useful for the
Goldwasser-Sipser protocol) and "almost k-wise"
independence (Nov 4-16);
- counting classes (Nov 18, 23);
- brief coverage of decision trees (Nov 23);
- communication complexity (Nov 25);
- circuit lower-bounds (Nov 30);
- PCP and the hardness of approximation (Dec 2, 7), and
- quick coverage of natural proofs, very brief look at quantum complexity,
and recap of the course (Dec 9).
Grading: Homework 30%, Contribution to Wikipedia 10%,
Class participation 5%, Midterm 25%, and Final 30%. To get full credit
for class participation, you should minimally participate in class
discussion a few times, and/or meet me during the office hours at least
once. Homework should be stapled and submitted on time; late homework will
not be accepted. There will be five or six graded HWs, and
(perhaps) a few ungraded ones. You will do the HW in groups of two
(with perhaps one group of three).
Mid-Term and Final Exam
The mid-term will be take-home, given on Oct. 21st and due by 11:59PM on
Oct. 26th: you can email it to me, return it to me in class, or slip it
under my office door.
The final exam will be in class on Friday, Dec 18, 8-10 AM: you can bring
your own course notes, and no other material.
Students are strongly encouraged to complete their course evaluations;
the site is here, and
will be open in the first half of December.
Students claiming a excused absence must apply in writing and furnish
documentary support (such as from a health-care professional who treated
the student) for any assertion that the absence qualifies as an excused
absence. The support should explicitly indicate the dates or times the
student was incapacitated due to illness. Self-documentation of illness
is not itself sufficient support to excuse the absence. An instructor
is not under obligation to offer a substitute assignment or to give a
student a make-up assessment unless the failure to perform was due to
an excused absence.
Academic Accommodations for Disabilities
Any student eligible for and requesting reasonable academic accommodations
due to a disability is requested to provide, to the instructor in office
hours, a letter of accommodation from the Office of Disability Support
Services (DSS) within the first two weeks of the semester.
The University of Maryland, College Park has a nationally recognized
Code of Academic Integrity, administered by the Student Honor Council.
This Code sets standards for academic integrity at Maryland for all
undergraduate and graduate students. As a student you are responsible
for upholding these standards for this course. It is very important for
you to be aware of the consequences of cheating, fabrication,
facilitation, and plagiarism. For more information on the Code of
Academic Integrity or the Student Honor Council, please visit
To further exhibit your commitment to academic integrity, remember to
sign the Honor Pledge on all examinations and assignments: "I pledge on
my honor that I have not given or received any unauthorized assistance
on this examination (assignment)."