Lecture Summaries

These lecture summaries can be viewed as the "past tense" course syllabus. They are intended for people who missed the class, or would like to briefly recall what was going on. Occasionally, I will include brief plan for future lectures, but do not count on it.

. Administrivia, introduction. What is "theory of computation": finite automata, computability, complexity, "special topics". Introduction to Turing Machines. Recursively Enumerable and Decidable Languages. Examples.**Lecture 01: Tue, Jan 21**__Read__: Sipser, review chapters 1,2, read section 3.1. Variations of Turing machines including non-determinism. Church-Turing Thesis. Examples of decidable languages from finite automata theory. Universal Turing Machine.**Lecture 02: Thu, Jan 23**__Read__: Sipser, section 3.2,3.3,4.1. More example from finite automata theory. Halting Problem. Undecidability. Closure properies of recursive and r.e. languages.**Lecture 03: Tue, Jan 28***R*is the intersection of*RE*and*coRE*. Examples of undecidable problems.__Read__: Sipser, section 4.2,5.1; Papadimitriou, chapter 3. Oracle Turing machines. Reductions. Turing reductions, mapping reductions, their properties. Techniques to show undecidability including how to show a language is not**Lecture 04: Thu, Jan 30***RE, coRE*and their union. Rice's theorem.__Read__: Sipser, section 5.1,5.3,6.3. Method of Configuration Histories or how to compare apples and oranges. "Natural" undecidable problems: some CFG problems, Post's Correspondence Problem.**Lecture 05: Tue, Feb 4**__Read__: Sipser, section 5.2. Warm-up: program that prints itself. Recursion Theorem and its many applications (simpler undecidability proofs, Rice's theorem, fixed point theorem, minimal length TMs, later Godel incompleteness theorem).**Lecture 06: Thu, Feb 6**__Read__: Sipser, section 6.1. Introduction to Logic. First order logic: vocabularies, sentences and models (or interpretations). Inference. True(M) = {Theorems true in model M} vs Th(G) = {Theorems which always follow from axioms G, in any model}. Validity = Th(empty). 3 fundamental questions of logic: (1) Is True(M) decidable?; (2) Is Th(G) decidable; (3) when can we axiomatize M: find "simple" G s.t. True(M) = Th(G).**Lecture 07: Tue, Feb 11**__Read__: Sipser, section 6.2, Papadimitriou 5.1-5.4. Godel's completeness theorem: theorem T is true in every model where axioms A are true iff T can be "systematically derived" from A. Justifies concepts of "theorem" and defines "provable". True(N,+) is decidable. Simple version of Godel's incompleteness: True(N,+,times) is undecidable. Corollary: some true statement about integers is not provable in any axiom system. Explicit construction using recursion theorem.**Lecture 08: Thu, Feb 13**__Read__: Sipser, section 6.2, Papadimitriou 5.5, 6.2, 6.3, lecture notes. Extension to show that Validity, Th(RA), Th(Peano) are all undesidable, recursive inseparability of Th(RA) and UNSAT. Relativization. Arithmetic hierarchy of "more and more undecidable" problems:**Lecture 09: Tue, Feb 18****Sigma_n**and**Pi_n**. Kleen's hierarchy theorem, Post's logical characterization. Completeness, complete problems in**Sigma_n**and**Pi_n**.__Read__: Papadimitriou 6.1, 6.3, lecture notes. Introduction to Complexity theory. Time Complexity. Linear speedup. Universality of polynomial time. Class**Lecture 10: Thu, Feb 20****P**, Examples of problems in**P**.__Read__: Sipser, sec 7.1-7.2, Papadimitriou, sec. 1.1,1.2,2.4.. Class**Lecture 11: Tue, Feb 25****NP**, examples of problems in**NP**.**P**vs**NP**question. Reductions, completeness and their importance for**P**vs**NP**question. Existence of**NP**-complete problems (trivial).*Natural***NP**-complete problems: SAT, CLIQUE, 3-COLOR, etc. Cook-Levin theorem and its implications.__Read__: Sipser, sec. 7.3-7.4, Papadimitriou, sec. 8.1-8.2.. Proof of Cook-Levin's theorem. Reductions, gadgets, and millions of other**Lecture 12: Thu, Feb 27****NP**-complete problems: 3SAT, Vertex-Cover, Hamiltionian Cycle, TSP, etc.__Read__: Sipser, 7.4-7.5, Papadimitriou, sec. 8.2, 9.. Search Classes**Lecture 13: Tue, Mar 4****FP**and**FNP**, completeness of FSAT, self-reducibility of SAT,**FP**=**FNP**iff**P**=**NP**. Class**TFNP**of total search problems (factoring).**NP**-hardness, class**coNP**,**NP**=**coNP**question, impossibility of**NP**-hardness in**TFNP**(e.g., factoring). Problems in**NP**intersection**coNP**.__Read__: Papadimitrious, sec. 10.1, 10.3.. (1) Existence on non-**Lecture 14: Thu, Mar 6****NP**-complete languages; (2) unary languages cannot be**NP**-complete; (3) Oracle separation between**P**and**NP**: explicit construction + random oracle separates with probability 1.__Read__: Papadimitriou, sec. 14.1-14.3.. Ways to deal with**Lecture 15: Tue, Mar 11****NP**-completeness: randomization, input restrcitions, average-case analysis and approximation algorithms. Brief introduction to approximation algorithms and hardness of approximation. Case of TSP: hard to approximate unrestricted instances, constant approximation for metric TSP, PTAS for Euclidean TSP. Vertex Cover. Classes of optimization problems: (a) PTAS (Euclidean-TSP, Knapsack); (b) O(1)-approximation (Vertex Cover, Metric TSP, MAX-SAT); (c) polylog(n)-approximation (Set-Cover, Dominating Set); (d) n^{delta}-approximation (Clique, Closest-Vector).__Read__: Papadimitriou, skim sec. 13, Sipser, sec. 10.1.. Space Complexity. General relations between space and time. Reachability method. Savitch's theorem. Classes**Lecture 16: Thu, Mar 13****PSPACE**and**NPSPACE**, their equality.**NP**in**PSPACE**.__Read__: Sipser, sec. 8.1-8.2, Papadimitriou, sec. 7.3..**Lecture 17: Tue, Mar 25****PSPACE**-completeness. Some complete problems: TQBF, Generalized Geography, Emptiness of L(NFA). Winning strategies for Games.__Read__: Papadimitriou, sec. 19.1, Sipser, sec. 8.3.. Sublinear space model. Logarithmic space. Classes**Lecture 18: Thu, Mar 27****L**and**NL**. Log-space reductions.**NL**-complete problems (REACHABILITY, 2SAT).**NL**=**coNL**.__Read__: Papadimitriou, sec. 16.1, Sipser 8.4-8.5..**Lecture 19: Tue, Apr 1****P**-completeness (circuit value, maxflow, linear programming). Circuits. Relation to TMs. Uniformity. Parallel computation. Classes**NCi, NC**, and their relation to**L, NL, P**. Time and space hierarchy theorems (as corollaries, separation of**P**and**EXP**,**NL**and**PSPACE**).__Read__: Sipser, 10.5, sec. 9.1, 9.3, Papdimitriou, sec. 7.2, 8.2, 15.1, 15.3.. Randomized Computation and its importance. Randomized test for primality (now outdated). Schwartz-Zippel lemma, randomized test for polynomial identity. Applications: (1) testing equivalence of read-once branching programs; (2) symbolic determinants; (3) efficient communication protocol for testing string equality. Class**Lecture 20: Thu, Apr 3****PP**and its inadequacy (**NP**belongs to**PP**). Class**BPP**.__Read__: Sipser, sec. 10.2.. Aplification lemma for**Lecture 21: Tue, Apr 8****BPP**. Other randomized complexity classes:**RP**,**coRP**and**ZPP**.**ZPP**equals**RP**intersection**coRP**.**RP**belongs to**NP**intersection**BPP**. Class**P/poly**.**BPP**belongs to**P/poly**. Same result is unlikely for**NP**.__Read__: Papadimitriou, sec. 11.1, 11.2, 11.4.. Polynomial hierarchy**Lecture 22: Thu, Apr 10****PH**. Existence of complete problems for various levels of**PH**(all special cases of TQBF). Containment in**PSPACE**. Standard assumption:**PH**does not "collapse".**NP**does not belong to**P/poly**under this assumption.**BPP**belongs to the second level of the hierarchy (**NP^NP**). Mention Toda's theorem:**PH**belongs to**P^PP**. Ideas of random walk (randomized algorithm for 2SAT). Randomized space-bounded complexity classes (**BPL**,**RL**,**coRL**,**ZPL**). Always halting versus non-always halting classes (non-always halting radomized classes all collapse to**NL**). Random walks on graphs, cover times. Test for undirected connectivity: USTCONN belongs to**RL**(mention can extend to**ZPL**, also that belongs to**SPACE(log^{4/3} n)**).__Read__: Papadimitriou, sec. 17.2, 16.3.. Is randomness necessary? Derandomization techniques: (1) specific (method of conditional probabilities, example for MAX-CUT), (2) general (pseudorandom generators); (3) weaken the assumption of perfect unbiased randomness (imperfect random sources). Survey of space-bounded derandomization: Nisan's generator,**Lecture 23: Tue, Apr 15****BPL**belongs to**TIMESPACE(poly(n),log^2 n)**(mention**BPL**belongs to**SPACE(log^{3/2} n)**), Nisan-Zuckerman generator (randomness is linear in space), conjecture that**L=BPL**(and different from**NL**). Brief survey on time-bounded derandomization: pseudorandom generators using cryptography, hardness vs. randomness (**P=BPP**unless every problem in**E**has subexponential size circuits).__Read__: class notes. Imperfect random sources. Extractable sources (von Neumann trick, bit-fixing sources, markov's chains). SV-sources. Impossibility of deterministic extraction. Different entropy notions and min-entropy. Statistical distance. Weak sources and (strong) randomness extractors. Non-explicit construction and optimal parameters.**Lecture 24: Thu, Apr 17**__Read__: handout. Pairwise indepepndent hash functions and the leftover hash lemma. Block sources and strong extractors for block sources. Simulating**Lecture 25: Tue, Apr 22****BPP**using SV-sources. State-of-the-art extractors: parameters and constructions. Simulating**BPP**using weak sources.__Read__: handout, Papadimitriou, sec. 11.3.. Introduction to interactive protocols. Class**Lecture 26: Thu, Apr 24****IP**, GNI example. Zero-knowledge. Honest verifier vs. any verifier. Classes**HV-PZK**and**PZK**. GI example. Relation to**NP**and**BPP**.__Read__: Sipser, Sec. 10.4, Papadimitriou, pp. 289-293..**Lecture 27: Tue, Apr 29****IP=PSPACE**(arithmetization technique). Arthur-Merlin games and perfect completeness. Private coins = public coins:**IP(r)**belongs to**AM(r+2)**.**MA**belongs to**AM**. Collapse theorem: for constant r>2,**AM(r) = MA(r) = AM(2) = AM**. Universality of**AM**.__Read__: Sipser, sec. 10.4, Papadimitriou, pp. 474-480..**Lecture 28: Thu, May 1****coNP**in**AM**implies the hierarchy collapses. Refereed games and conflicting provers (class**RG**).**RG=EXP**. Rounds and private/public coins:**RG(1,private) = PSPACE = RG(poly,public)**. Multiple provers, class**MIP**. Zero-knowledge proofs for**NP**with two provers. Oracles vs. provers, class**PCP**.**PCP=MIP=MIP(2)=NEXP**.**PCP**-characterization of**NP**:**NP=PCP(O(log n), O(1))**. Applications to inapproximability.__Read__: Papadimitriou, pp. 506-508, sec. 13.3, Feige/Kilian paper, lecture notes.

Back to the course page