G22.3350-001 Honors Theory of Computation, Lecture Summaries

# Honors Theory of Computation (G22.3350) 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.
• Lecture 01: Tue, Jan 21. Administrivia, introduction. What is "theory of computation": finite automata, computability, complexity, "special topics". Introduction to Turing Machines. Recursively Enumerable and Decidable Languages. Examples.

• Lecture 02: Thu, Jan 23. Variations of Turing machines including non-determinism. Church-Turing Thesis. Examples of decidable languages from finite automata theory. Universal Turing Machine.

• Lecture 03: Tue, Jan 28. More example from finite automata theory. Halting Problem. Undecidability. Closure properies of recursive and r.e. languages. R is the intersection of RE and coRE. Examples of undecidable problems.

• Lecture 04: Thu, Jan 30. Oracle Turing machines. Reductions. Turing reductions, mapping reductions, their properties. Techniques to show undecidability including how to show a language is not RE, coRE and their union. Rice's theorem.

• Lecture 05: Tue, Feb 4. Method of Configuration Histories or how to compare apples and oranges. "Natural" undecidable problems: some CFG problems, Post's Correspondence Problem.

• Lecture 06: Thu, Feb 6. 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 07: Tue, Feb 11. 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 08: Thu, Feb 13. 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 09: Tue, Feb 18. 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: Sigma_n and Pi_n. Kleen's hierarchy theorem, Post's logical characterization. Completeness, complete problems in Sigma_n and Pi_n.

• Lecture 10: Thu, Feb 20. Introduction to Complexity theory. Time Complexity. Linear speedup. Universality of polynomial time. Class P, Examples of problems in P.

• Lecture 11: Tue, Feb 25. Class 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.

• Lecture 12: Thu, Feb 27. Proof of Cook-Levin's theorem. Reductions, gadgets, and millions of other NP-complete problems: 3SAT, Vertex-Cover, Hamiltionian Cycle, TSP, etc.

• Lecture 13: Tue, Mar 4. Search Classes 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.

• Lecture 14: Thu, Mar 6. (1) Existence on non-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.

• Lecture 15: Tue, Mar 11. Ways to deal with 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).

• Lecture 16: Thu, Mar 13. Space Complexity. General relations between space and time. Reachability method. Savitch's theorem. Classes PSPACE and NPSPACE, their equality. NP in PSPACE.

• Lecture 17: Tue, Mar 25. PSPACE-completeness. Some complete problems: TQBF, Generalized Geography, Emptiness of L(NFA). Winning strategies for Games.

• Lecture 18: Thu, Mar 27. Sublinear space model. Logarithmic space. Classes L and NL. Log-space reductions. NL-complete problems (REACHABILITY, 2SAT). NL = coNL.

• 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.

• Lecture 20: Thu, Apr 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 PP and its inadequacy (NP belongs to PP). Class BPP.

• Lecture 21: Tue, Apr 8. Aplification lemma for 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.

• Lecture 22: Thu, Apr 10. Polynomial hierarchy 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)).

• Lecture 23: Tue, Apr 15. 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, 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).

• Lecture 24: Thu, Apr 17. 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 25: Tue, Apr 22. Pairwise indepepndent hash functions and the leftover hash lemma. Block sources and strong extractors for block sources. Simulating BPP using SV-sources. State-of-the-art extractors: parameters and constructions. Simulating BPP using weak sources.