Computational Complexity Theory

Computational Complexity Theory

Home             Information             Lectures             Homeworks             References
This page contains the "static" information about this course. Any changes in these will be announced/highlighted to the mailing-list of participants of the course by email.

Basic Information

Instructor : Jayalal Sarma M.N.
Office : FIT 4-606-3, Ph. 1683
Email : jayalal@tsinghua

Lectures : Mondays and Wednesdays, 1:30-3pm, at Room 1-222, FIT Building
Office hours dedicated for the course : Wednesdays, 3-4pm

About the Course

A (slightly advanced) course in Computational Complexity Theory. Computational Complexity Theory is the study of efficient computation and its fundamental limitations. The theory helps us to state questions about this in a precise way and provide qualified answers to them. To state some examples, how much resources is required to solve concrete computational problems? Does the use of randomness or parallelism make computations significantly faster? However, it turns out that the hardest thing to prove about the models is that they cannot solve a given problem within particular resource constraints. Such ``lower bounds'' are currently obtainable only when the model is very specialized or the constraints are very severe. Inherent limitations of the currently known techniques is also something that is currently explored on the research frontier of complexity theory.

The course will give a quick introduction to the classical results and techniques in complexity theory and thereafter cover (selected) newer results and areas. The choice of topics is based on the view that the course should provide a platform for the current topics of research in the area of complexity theory. We might possibly be skipping some of the basic material in a standard complexity theory course. In general, we hope (or want) to touch upon most of the topics below roughly divided into 28-30 lectures in total. We may choose to slightly deviate (which I will indicate in italics) from this plan as the course progresses. I shall provide references to read up the topics that we skip.

Coursework and Grading

Three parameters :

Problem Sets: A set of problems (problem sets) will be posted (here and here) based on every 8 lectures (thats the plan!). All students who are crediting the course are required to turn in the solutions, which will be graded and returned before 2 weeks after the submission date. The grades from homeworks will be contributing towards 30% of the final grade. Here are some guidelines for working on the problem sets:

Scribing Notes: Each student is required to scribe three lectures; the scribed notes will count for 30% of the grade. A final project will count for 40% of the grade.

Final Project: The project will involve studying a few (one or two) papers on an advanced topic not covered in class, writing a short report, and giving a 30-minute presentation in class. We will list down suggestions for the topics in the webpage. The students could divide themselves into groups. Two-people collaborations are possible and particularly recommended when the topic chosen is broad. We will meet for a 3-hour session on Sat, Jun 13 for the presentations.