CMSC 652, Complexity Theory, Fall 2009, MW 12:30-1:45PM

Instructor: Aravind Srinivasan
Office: AVW 3263, Phone: 301-405-2695
Instructor's office Hours: Mon 3-5 pm and Fri 12-1 pm in AVW 3263
Course Time and Location: MW 12:30-1:45 PM, CMSC 3120
Book: No required textbook, but Arora-Barak is recommended.

Course Webpage:

Announcements and Links:

Course Description: The following is an approximate schedule:

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.

Course Evaluation

Students are strongly encouraged to complete their course evaluations; the site is here, and will be open in the first half of December.  

Excused Absences

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.

Academic Integrity

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)."