
Instructor  Dominique Unruh <<surname> at ut dot ee> 
Teaching assistant 
Prastudy Fauzi <<givenname> at ut dot ee> 
Lecture Period  August 30, 2016 – December 13, 2016 
Lectures  Tuesdays, 10:1511:45, Paabel, room 218
(Unruh; may sometimes be switched with practice) 
Practice sessions 
Tuesdays, 12:1513:45, Paabel, room 218
(Unruh/Fauzi) 
Course Material  Blackboard photos (of practice), and exam study guide. 
Language  English 
Mailing list  utcomplexity@googlegroups.com 
Exam  TBA 
Contact  Dominique Unruh <<surname> at ut dot ee> 
20160830 (lecture)  Intro: what is complexity theory for. Ohnotation. Languages/decision problems. Turing machines. ChurchTuring thesis. Universal TM. Uncomputable functions. Halting problem. The classes DTIME, P, NP. Strong ChurchTuring thesis. (Double lecture)  [video] 
20160906 (lecture)  Karp reductions. NPhard. NPcomplete. Satisfiability. CNFformulas. CookLevin theorem (with proof).  [video] 
20160906 (practice)  Turing machine for palindrome testing. Turing machine for simulating a normal computer (partial). (Tore)  
20160913 (practice)  INDSET is NPhard. SAT reduces to INDSET. (RaulMartin)  
20160920 (lecture)  coNP and coNPcompleteness (Sec. 2.6.1). NPdecision vs. NPsearch problems (Sec. 2.5). What if P=NP, what if L NPhard? (Sec. 2.7.3, 2.7.6). BakerGillSolovay (BKS) theorem (Sec. 3.4).  [video] 
20160920 (practice)  Timehierarchy theorem. (Adriano)  
20160927 (lecture)  Randomized algorithms intro (Chap. 7 intro & Sec. 7.2.2). Polynomial identity testing (Sec. 7.2.3).  [video] 
20160927 (practice)  Oracle Turing machines. P^P=P. SAT^L is NP^L complete. (Tore)  
20161004 (lecture)  Probabilistic TM (Sec. 7.1). Class BPP (Sec. 7.1). Amplification in BPP (Sec. 7.4.1). RP (Sec. 7.3). ZPP (Sec. 7.3). BPP in EXP.  [video] 
20161004 (practice)  BPL (boundederror probabilistic logspace, Sec. 7.7) is in P.  
20161011 (lecture)  Space complexity (Chap 4). Classes L and PSPACE (Sec. 4.2). TQBF is PSPACEcomplete (Sec. 4.3, proof only for "in PSPACE"). PSPACE and twoplayer games (Sec. 4.3).  [video] 
20161011 (practice)  Randomized polynomialtime algorithm for perfect matching. Algorithm for ZPP that never errs.  
20161018 (lecture)  Polynomialhierarchy. Classes Σip, Πip, PH. Relation of PH to P, NP, PSPACE. (Sec. 55.2 and 5.5)  [video] 
20161018 (practice)  TQBF is PSPACEhard. (Tore)  
20161025 (lecture)  Boolean circuits (Sec. 6.1). P/poly (Sec. 6.1). UHALT in P/poly (Sec. 6.1.1). P in P/poly (Sec. 6.1.1). Nonuniform hierarchy theorem (Sec. 6.6). Puniform circuits = P (Sec. 6.2).  [video] 
20161025 (practice)  NP not in P/poly unless PH collapses (KarpLipton, Sec. 6.4). (Ashish)  
20161101 (lecture)  Interactive proofs (Sec. 8.1.2). Classes IP[k], IP (Sec. 8.1.2). Classes MA, AM[k], AM (Sec. 8.2). GNI (graph nonisomorphism) is in IP[2] (Sec. 8.1.3). And in AM[2] (only mentioned, Sec. 8.2.1). IP[k] in AM[k+2] (only mentioned, GoldwasserSipser, Sec. 8.2.1).  [video] 
20161101 (practice)  BPP in P/poly (Sec. 7.5.1). (Dominique).  
20161108 (lecture)  If graphiso is NPcomplete, PH collapses. IP=PSPACE (w/o proof). Quantum computing (intro). Formalization of quantum mechanics (started).  [video] 
20161108 (practice)  Evaluating quantum circuits.  
20161117 (lecture)  Formalization of quantum mechanics (ctd.). Simon's algorithm. Class BQP. BPP in BQP. BQP notin BPP relative to oracle.  [video] 
20161117 (practice)  CHSH games (classical and quantum strategies)  
20161122 (lecture)  Cryptography (Chap 9). The need for P!=NP (Lemma 9.2). Oneway functions. Oneway functions imply encryption.  [video] 
20161122 (practice)  MerkleHellman knapsackbased cryptosystem  
20161129 (lecture)  Class PCP. GNI in PCP(poly,1). W/o proof: "PCP Theorem" NP=PCP(log,1) Constraint satisfaction problems (qCSP). PCP Theorem implies: qCSP hard to approximate.  [video] 
20161213 (lecture)  QUADEQ. WalshHadamard codes. PCPproof system for QUADEQ. NP in PCP(poly,1).  [video] 
Out 
Due 
Homework 
Solution 

20160830  20160908  Homework 1  Solution 1 
20160906  20160922  Homework 2  Solution 2 
20160927  20161004  Homework 3  Solution 3 
20161006  20161013  Homework 4  Solution 4 
20161012  20161020  Homework 5  Solution 5 
20161020  20161027  Homework 6  Solution 6 
20161026  20161103  Homework 7  Solution 7 
20161102  20161110  Homework 8  Solution 8 
20161111  20161117  Homework 9  Solution 9 
20161118  20161124  Homework 10  Solution 10 
20161126  20161203  Homework 11  Solution 11 
20161202  20161213  Homework 12  Solution 12 
Complexity theory (or computational complexity theory) is the study of how hard computational problems are. Could it be that there are fast algorithms, e.g., for finding optimal routes? Or will any search for such algorithms be doomed from the start? What are the principal limitations of computation? Questions like this lie in the core of complexity theory. Complexity theory itself is one of the foundational areas in computer science, and it is hard to understand the theory of computer science without a sound background in complexity theory. Complexity theory is especially important for the cryptographer, as complexity theory shows up in disguise in many cryptographic security proofs.
This course will introduce you to the basics of complexity theory. You will learn the basic terminology and notions in complexity theory and learn to reason like a complexity theorist. Possible topics include (but are not limited to):
The precise choice of subjects may vary, preferences of the audience can be taken into account.
Required book (will be available in the library): "Computational Complexity: A Modern Approach" by Arora and Barak, Cambridge University Press, 2009. A draft of the book is freely available here. The lecture will mostly follow part I of this book.
Complexity Zoo: A very extensive list of complexity classes. http://complexityzoo.uwaterloo.ca/. A version for "beginners" is http://complexityzoo.uwaterloo.ca/Petting_Zoo.