-
-
Lectures: Tuesdays & Thursdays, 9:30 - 10:45 a.m. @ ECST 1B21.
-
Office hours: Monday 3:00 - 4:00 p.m. and Wednesdays 3:00 - 4:00 p.m. @ ECOT 624.
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..).
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.
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.
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.
Apart from textbooks, I find on-line blogs to be wonderful places to gain insights into the
material covered in class:
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.
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.
