Portrait of Ada Lovelace by British painter Margaret Sarah Carpenter (1836)
Alan Turing by Jin Wicked
Administration
Complexity Theory • COMPSCI 290.3
Spring 2015
Instructor: Pankaj K. Agarwal
TAs: Abhinandan Nath and Jiangwei Pan
Time: Tue, Thu 3:05-4:20 pm
Location: LSRC D243
Office Hours: Tue, Fri 2:00-3:00pm (D214A LSRC Bldg)
Course Synopsis
This course covers theory of computation and complexity theory. Topics include:
- Turing machines: Basics, nondeterministic turing machines, tape compression, linear speedup, universal turning machines.
- Undecidability: Halting problem, recursive and recursively enumerable languages, recursive functions.
- Complexity classes: Complexity measures, hierarchy theorems, relations among complexity measures, regular languages, reducibilities, complete problems.
- NP: NP-Completeness, Cook's theorem, other NP-Complete problems, co-NP.
- Beyond NP: PSPACE, polynomial hierarchy, #P, EXPTIME, EXPSPACE, alternation.
- Randomized computation: Randomized TM, randomized complexity classes, randomized reductions.
- Boolean circuits: Size lower bounds, uniform circuits, NC, P-Completeness.
- Interactive proofs: Interactive proof systems, IP=PSPACE, multiprover interactive proofs, program checking.
- Cryptography: Perfect secrecy, computational security, one way functions, zero knowledge.
- Approximability and PCP theorem: Approximation algorithms to NP-hard problems, non-approximability, MAXSNP, PCP, PCP vs. NP.
- Quantum computation: Quantum superposition and qubits, quantum computation and BQP, search algorithm, factorization.
Prerequisites
COMPSCI 230 and 330, or equivalent courses. This course requires undergraduate background in discrete mathematics and algorithms
Textbooks
[AB] S. Arora and B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press.
[Sip] M. Sipser, Introduction to the Theory of Computation, CENGAGE Learning, Boston.
[Pa] C. H. Papadimitriou, Computational Complexity, Addison Welsley.
Reference Books
[G] O. Goldreich, Complexity: A Conceptual Perspective, Cambridge University Press.
[HMU] J. Hopcroft, R. Motwani, J. Ullman, Intriduction to Automata, Languages, and Computation, Addison Welesley.
Grading
- Assignments (four out of five): 30%
- Midterm exams: 30%
- Final exam: 40%
- Both midterm and final will be in-class closed-book exams, and the final exam will be take home.
- Students are required to use Latex or MS-Word for writing their assignments and to submit the pdf files of their assignments.
- No credit is given for late solutions.
Collaboration Policy
For assignments, collaboration among students is permitted, but students MUST write up solutions independently on their own and LIST your collaborators for each problem. The assignment questions may be similar to questions on problem sets from past offerings of this course or courses at other universities. Using any preexisting solutions from these or any other sources is strictly prohibited.
page top