
Instructor  Dominique Unruh <<surname> at ut dot ee> 
Teaching assistant 
Prastudy Fauzi <<givenname> at ut dot ee> 
Lecture Period  September 9, 2014  December 16, 2014 
Lectures  Tuesdays, 10:1511:45, room 403
(Unruh; may sometimes be switched with practice) 
Practice sessions 
Tuesdays, 12:1513:45, room 122
(Unruh) 
Course Material  Blackboard photos (of practice), and exam study guide. 
Language  English 
Mailing list  utcomplexity@googlegroups.com 
Exam  January 8, 2015, 14:0017:00, room 403 
Contact  Dominique Unruh <<surname> at ut dot ee> 
20140909 (lecture)  Intro: what is complexity theory for. Ohnotation. Languages/decision problems. Turing machines. 
20140909 (practice)  Turing machine for palindrome testing. Turing machine for simulating a normal computer. (Yauhen) 
20140916 (lecture)  ChurchTuring thesis. Universal TM. Uncomputable functions. Halting problem. The classes DTIME, P, NP. Strong ChurchTuring thesis. 
20140916 (practice)  Timehierarchy theorem. (Janno) 
20140923 (lecture)  Karp reductions. NPhard. NPcomplete. Satisfiability. CNFformulas. CookLevin theorem (with proof). 
20140923 (practice)  INDSET is NPhard. SAT reduces to INDSET. (Yauhen) 
20140930 (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) 
20140930 (practice)  Oracle Turing machines. SAT^L is NP^L complete. (Ivo) 
20141007 (lecture)  BakerGillSolovay (BKS) theorem (Sec. 3.4). Randomized algorithms intro (Chap. 7 intro & Sec. 7.2.2). 
20141007 (practice)  Polynomial identity testing (Sec. 7.2.3). (Vootele) 
20141014 (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. 
20141014 (practice)  BPL (boundederror probabilistic logspace, Sec. 7.7) is in P. (Yauhen) 
20141021 (lecture)  Space complexity (Chap 4). Classes L and PSPACE (Sec. 4.2). TQBF is PSPACEcomplete (Sec. 4.3). PSPACE and twoplayer games (Sec. 4.3). 
20141021 (practice)  Palindrom in L. Hex in PSPACE. (Mayuresh) 
20141028 (lecture)  Polynomialhierarchy. Classes Σip, Πip, PH. Relation of PH to P, NP, PSPACE. (Sec. 55.2 and 5.5) 
20141028 (practice)  If Σip=Πip, PH collapses (Thm 5.4(1)). (Yauhen) 
20141104 (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). NP not in P/poly unless PH collapse (KarpLipton, Sec. 6.4). Nonuniform hierarchy theorem (Sec. 6.6). Puniform circuits = P (Sec. 6.2). 
20141104 (practice)  BPP in P/poly (Sec. 7.5.1). (Ivo). 
20141111 (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] (Sec. 8.2.1). IP[k] in AM[k+2] (GoldwasserSipser, Sec. 8.2.1). 
20141111 (practice)  IP with deterministic verifier (dIP) = NP (Sec. 8.1.1). IP in PSPACE (Ex. 8.1(b)). (Yauhen) 
20141118 (lecture)  If graphiso is NPcomplete, PH collapses. IP=PSPACE (w/o proof). Quantum computing (intro). Formalization of quantum mechanics. 
20141118 (practice)  Evaluating quantum circuits. 
20141125 (lecture)  Formalization of quantum mechanics (ctd.). Simon's algorithm. Class BQP. BPP in BQP. BQP notin BPP relative to oracle. 
20141125 (practice)  ... 
20141202 (lecture)  Cryptography (Chap 9). The need for P!= NP (Lemma 9.2). One way functions imply CPA secure encryption. 
20141202 (practice)  Breaking the MerkleHellman knapsackbased cryptosystem. 
20141209 (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. 
20141209 (practice)  What hardness of approximation does NP in PCP(poly,1) imply. (No definite conclusion reached.) 
20141216 (lecture)  QUADEQ. WalshHadamard codes. PCPproof system for QUADEQ. NP in PCP(poly,1). 
20141216 (practice)  QUADEQ is NPcomplete. 
Out / due 
Homework 
Solution 


20140916  20140925  Homework 1  Solution 1 
20140926  20141003  Homework 2  Solution 2 
20141001  20141009  Homework 3  Solution 3 
20141009  20141016  Homework 4  Solution 4 
20141016  20141023  Homework 5  Solution 5 
20141030  20141106  Homework 6  Solution 6 
20141106  20141113  Homework 7  Solution 7 
20141113  20141120  Homework 8  Solution 8 
20141120  20141127  Homework 9  Solution 9 
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.