CSCI 7154: Complexity of Computation (Fall 2010)

General Information

This course will cover topics related to computational complexity theory for reasoning about the time and space requirements for computing solutions to problems. This theory has been at the forefront of CS research driven by open problems such as the P =(?) NP problem.

Our foci in this course will be to understand the basic results in computational complexity theory and a few interesting applications to fields such as computer security (public key cryptography, zero knowledge, etc..) and formal verification (solving SAT and other decision problems, program checking, etc..).

Target Audience

  • Students broadly interested in CS Theory.
  • Students interested in learning about a 40 year old open problem (millenium challenge).


There are no formal prerequisites. However, it is essential to possess one or more of the following:

  • [Informal] Ability to understand and prove mathematical propositions rigorously.
    • Having successfully completed (applied) math classes at the undergraduate or graduate level, for example.
  • Basic CS Theory at the level of CSCI 3104 (Algorithms) and/or CSCI 3434 (Theory of Computation).
  • Having taken CSCI 5454 (graduate theory of computation) is a big plus.

Course Grading

There will be three parts to the overall grade:

  • Weekly homework assignments for the first 80% of the course. These will count for 70% of the grade.
  • Course Project: The project will involve starting off from a paper (or a survey) and reading, understanding some aspect of the material deeper. Often, the student may need to do a literature search and read other papers in the process. These will count for 20% of the grade. Short project presentations will be held in the last week of classes.
  • An additional 10% will be based on class participation: being there in class, asking questions and pointing out instructor mistakes.

The final grade will be determined as a total of the homework grades, the project grade and the participation. There will be no “curving” or “relative grading”. Each person will be graded on her/his own performance!

Final Total Guaranteed Grade
75% or above A- or higher
60% or above B- or higher
50% or above C- or higher
>= 40% D- or higher
otherwise Fail/Incomplete


We will primarily use two textbooks (on reserve):

Arora & Barak's book is newer and more comprehensive. The course will follow this book. Nevertheless, the book by Papadimitriou is widely regarded as a classic. We will cover some material on Logic/Finite Model Theory from Papadimitriou's book.

Other Resources

Apart from textbooks, I find on-line blogs to be wonderful places to gain insights into the material covered in class:

Collaboration Policy

Informal: The collaboration policy for this course assumes that:

  • We are all here to learn this beautiful and wonderful part of CS theory for ourselves and will not let anything get into the way!!
  • We all enjoy solving problems ourselves, with help from our peers. Being handed the answer on a platter is no fun!

The collaboration policy is rather simple:

  • Inspiration is free: you may discuss homework assignments with anyone. You are especially encouraged to discuss solutions with your instructor and your classmates.
  • Plagiarism is forbidden: the assignments that you turn in should be written entirely on your own. While writing the assignment you are not allowed to consult any source other than the textbook(s) for the class, your own class notes or the lecture videos for the class. Copying/consulting from the solution of another classmate constitutes a violation of the course's collaboration policy.
  • Do not search for a solution on-line: You may not actively search for a solution to the problem from the internet. This includes posting to newsgroup or asking experts at other universities.
  • When in doubt, ask: If you have doubts about this policy or would like to discuss specifc cases, please ask the instructor.

The CU Boulder honor code is available online. You are expected to be aware of and to follow the honor code.

Topics Covered

A list of topics (liable to change) that will be covered (material that must be familiar from earlier classes will be covered at a faster pace).

  • Turing Machines: Time and Space Bounded Machines, Complexity Classes, Savitch's Theorem, Immerman-Szelepcsenyi Theorem.
  • NP-Completeness: Reductions, Completeness of 3-CNF SAT, NP-Complete Problems, Ladner's Theorem.
  • PSPACE-Completeness: Quantified Boolean Formulae (QBF), Games, PSPACE-Complete problems.
  • Polynomial-Hierarchy: Various properties of PH.
  • Logic and Finite Model Theory: Basics of model theory, Fagin's theorem, Immerman-Vardi theorem, characterization of PSPACE.
  • Circuit Complexity
  • Randomized Complexity Classes
  • Interactive Proofs
  • PCP and Hardness of Approximations
  • Quantum Complexity Classes
  • Advanced Topics: In-depth study of statistical properties of SAT and CSPs.
start.txt · Last modified: 2010/09/27 22:17 by srirams
Except where otherwise noted, content on this wiki is licensed under the following license:CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki