Computer Science 142 and Mathematics 167
Computational Complexity Theory (a.k.a. "Theocomp")
Syllabus, Fall 2008

Professor: Ran ("RON") Libeskind-Hadas
Office: Olin 1245
Phone: x18976
E-mail: hadas@cs.hmc.edu
Office Hours: Please see my schedule
Course Time and Location: Mondays and Wednesdays, 4:15-5:30 PM, in Jacobs B134

Course Homepage: www.cs.hmc.edu/courses/2008/fall/cs142

What Is This Course About?

This course is primarily about computational complexity theory, the study of the "hardness" of computational problems. However, we begin with a brief section on computability theory (some review from CS 81 but mostly new material), since a firm grounding in this area is necessary to understand some of the issues in complexity theory.

The course is divided into two parts: Part 1 of the course will be lecture-based and will cover the foundations of computability and complexity. In Part 2 of the course, you will select a topic in complexity theory, give a presentation to the rest of the class on your topic, and assign and grade homework problems on your presentation.

Here is a tentative list of topics:

Computability Theory

Computational Complexity Theory

Part 2 of the course will comprise student presentations of material related to this course. The objective of this part of the course is to develop the ability to read original research papers and present the material clearly in class. You will work with Ran in advance to select the topic, find the appropriate papers to read, and develop your in-class presentation. In addition, you will be asked to assign approximately two homework problems on your topic and you will grade these problems. These homeworks scores will count as required regular homework for your classmates.

Texts

There is no textbook for the course. Lectures will be self-contained. Some books will be placed on reserve in the library and this will be announced in class.

Attendance and Participation

On-time attendance in every class is absolutely required to pass the course. If you are sick or have a special reason for missing class, please contact Ran before the class that you will miss. Otherwise, you are expected to be in class. Please make sure to arrive on-time as a courtesy to the instructor and your classmates. Participation in class is also expected and is a component of the course grade.

Assignments

There will typically be one assignment each week, given on Wednesday and due the following Wednesday. All problem set submissions must be typeset, preferably using LaTeX. Assignments will be posted in both pdf and LaTeX source formats on the course web page.

Exams

There will be one exam in this course, an open-notes take-home exam on the material in Part 1 of the course. There will be no final exam.

Grades

The components of the course are worth the following: 
 
	Homework in Parts 1 and 2 of the course: 60% 
	Take-home Exam:  20%
	Part 2 presentation:  20%
Note that attendance is not factored into this breakdown, but is required in order to pass the course.

Collaboration Policy

Collaboration on homeworks is encouraged. This means that you may discuss approaches to solving a problem with anyone in the class. On each submitted homework, please indicate the names of all people with whom you discussed your solutions. Unless indicated otherwise, no written sources (other than your own notes) should be consulted in solving homework problems. There should be no collaboration on the take-home exam. All parties, including off-campus students, are expected to follow the Harvey Mudd Honor code.