Rex Lei, Office hours: 9:30am-11:30am on Monday (TA room), Email: rl2746@columbia.edu

Course Description:

In this course, we study Computational Complexity, one of the most active research areas of Theoretical Computer Science devoted to "understanding" the intrinsic hardness of computational problems / limitations of efficient algorithms. We will mostly follow the book of Papadimitriou during the first half of the semester. The book by Sipser is more introductory. Please read the related chapters if you need to review the definition of Turing machines and basic complexity classes. The book by Arora and Barak covers more advanced topics and active research areas. Some of the topics we cover in the second half of the semester can be found there. A list of topics we plan to cover in the course:

Diagonalization: Undecidability, time and space hierarchies

Basic complexity classes (P, NP, PSPACE ...)

Reductions and completeness

Interactive proofs: IP = PSPACE

Randomness as a resource and related complexity classes

Probabilistically checkable proofs and inapproximability

Nonuniform computational models

Decision tree lower bounds

Communication complexity

Circuit lower bounds

Prerequisites:

An introductory course on theory of computation, e.g., COMS 3261.

A course on algorithms, e.g., COMS 3137/3139 or 4231, will be helpful but is not required.

The course is mostly theoretical, so you should feel comfortable reading and working with math and proofs (Chapter 0 of Sipser's book is a good resource.) and general mathematical maturity will be assumed. Some knowledge of discrete mathematics and basic probability (e.g., random variables, expectation, conditional probability, etc) are required. We will not use any particular programming language in the course.

You should be familiar with Turing machines, though we will review it briefly in the first lecture. Read Chapter 3 of Sipser's book if necessary. You should be familiar with the asymptotic notation, e.g., Big-O.

Grading:

Homework (35%), in-class midterm (30%), final (35%)

Homework:

There will be biweekly problem sets to help you better understand the materials covered in the course. They will be assigned on Thursdays, posted here, and due two weeks later before the Thursday class. You may either submit a physical copy before class or send me the pdf file by email. The assignments must be written in LaTeX since it makes the math formulas look better and TA's life easier. Check this if you are not familiar with LaTeX. It should only take you 157 minutes at most.

Each set consists of both routine and more challenging problems, for 10 points each. You are encouraged to start early, and to make effective use of the office hours of the instructor and teaching assistant.

Most of the problems require one or two key ideas. Be concise when writing up the solutions, but make sure to give enough details to clearly present those key ideas. Learn from the writing style of the textbook how to rigorously and succinctly present a proof. Understandability will be an important factor considered in grading. You are discouraged from writing up long answers which you suspect are incorrect, in the hopes of picking up a point or two. You will get no point by doing this, and will receive a warning for the first violation. Any subsequent violation will be penalized by 10% off the whole set, due to the waste of TA time.

Homework Policy:

Late homeworks will not be accepted. Exceptions will be made only for exceptional circumstances (e.g., serious illness or family crisis).

The homework submitted must be written by yourself independently, without looking at anybody else's solutions.

You may discuss the problems with fellow students taking the class, teaching assistants and the instructor. If you collaborate, you must acknowledge clearly, at the beginning of each problem, the people you discussed with on that problem. You are expected to fully understand every single step of the solution, and must write up the solutions by yourself independently.

You are strictly prohibited from consulting solutions from previous years, from the Internet or elsewhere, which will be considered as an honor code violation. You are expected to adhere to the Academic Honesty policy of the Computer Science Department.

General Information:## Teaching Assistants:

## Course Description:

Prerequisites:Grading:## Homework:

must be written in LaTeXsince it makes the math formulas look better and TA's life easier. Check this if you are not familiar with LaTeX. It should only take you 157 minutes at most.## Homework Policy: