General Information:
  • Instructor: Xi Chen CSB 503, Office hours: Tuesday 3pm -- 6pm or by appointment
  • TA: Igor Carboni Oliveira CSB 516, Office hours: Friday 1:30pm -- 3:30pm
  • Location: 644 Mudd Building
  • Time: Tuesday 6:10pm -- 8:00pm
  • Textbook: Computational Complexity: A Modern Approach, by S. Arora and B. Barak. We will only use a few chapters of the book on lower bounds (in Part II: Lower bounds for concrete models). A draft of the book is available online here. Links to more references and materials will be posted on the Lectures page.

Course Description:
  • In this course, we focus on concepts and techniques developed in proving lower bounds for various models of computation, including decision trees, communication complexity, restricted (boolean and arithmetic) circuits. If time allows we will also touch on some of the recent lower bound results in property testing and data structures.

  • An introductory course on the theory of computation is required, e.g., COMS 3261.
  • While a course on complexity theory, e.g., COMS 4236, is not required, you should be familiar with those basic computational models like Turing machines and boolean circuits, as well as the asymptotic notation, e.g., Big-O.
  • The course is mostly theoretical, so you should feel comfortable reading and working with math and proofs. General mathematical maturity will be assumed. Some knowledge of discrete mathematics and basic probability theory (e.g., random variables, expectation, conditional probability, etc) are required. We will not use any particular programming language in the course.

  • Class participation and notes scribing (20%)
  • Biweekly assignments (40%)
  • Presentation (40%)

Course Requirements:

  • Participate in lectures and scribe notes. A group of one or two students is expected to scribe notes for each lecture. The notes, which should be a clear exposition of the materials covered, will be posted here within a week. Here is the LaTex template: Template.tex and Template.pdf. Check this if you are not familiar with LaTeX. It should only take you 157 minutes at most.
  • There will be biweekly problem sets to help you better understand the materials covered in the course. They will be assigned on Tuesdays after the class, posted here, and due two weeks later before the Tuesday class. 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. The assignments must be written in LaTeX since it makes the math formulas look better and TA's life easier.
  • 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.
  • A list of papers will be available before the end of September. You are expected to form a group of one or two students, pick a paper that you are interested in, and present it (both the results and key techniques) at the end of the semester. More information (e.g., the length of each presentation) will be decided later depending on the final enrollment.

Homework Policy:
  • Always email the TA before class with the pdf file of your homework, and don't forget to bring a hard copy of your homework to the class. The pdf files will *not* be graded, but may be used for verification purposes.
  • 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.