G22.3350-001 Honors Theory of Computation, Syllabus

# Honors Theory of Computation (G22.3350), Brief Syllabus

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: Wed, Jan 17. Administrivia, introduction. What is "theory of computation"? Introduction to DFA and regular languages: definition, simple closure properties. Read: Sipser, chap. 0, 1.1.
• Lecture 02: Mon, Jan 22. NFAs, equivalence of NFA and DFA, more closure properties, regular expressions, pumping lemma. Read: Sipser, chap. 1.2-1.3.
• Lecture 03: Wed, Jan 24. Context-free grammars, pushdown automata, equivalence of the two, pumping lemma for CFL's. Problem Set 1 out (on automata theory, due Monday Feb. 5). Read: Sipser, chap. 2.
• Lecture 04: Mon, Jan 29. Wrap up of automata theory. Introduction to Turing machines. Recursive and recursively enumerable languages. Read: Sipser, chap. 3.
• Lecture 05: Wed, Jan 31. Variations of Turing machines including non-determinism. Church-Turing Thesis. Examples of Decidable Languages. Universal Turing Machine. Halting Problem. Undecidability. Read: Sipser, chap. 4.
• Lecture 06: Mon, Feb 05. R is the intersection of RE and coRE. Examples of undecidable problems. Techniques to show undecidability: Turing reductions, mapping reductions, Rice's theorem. How to show a language is not RE/coRE. Read: Sipser, chap. 5, Papadimitriou, chap. 3.
• Lecture 07: Wed, Feb 07. Method of Configuration Histories. Undecidability of some CFG problems, Post's Correspondence Problem. Recursion Theorem. Problem Set 2 out (on computability, due Friday Feb. 23). Read: Sipser, end of Chap. 5, beginning of chap. 6.
• Lecture 08: Mon, Feb 12. More on Recursion theorem. Mentioning of Advanced Topics in Computability (arithmetic hierarchy, complete problems, Recursive inseparability, Kolmogorov's complexity). Wrap-up of Computability. Introduction to Logic (propositional calculus). Read: Sipser, finish chap. 6, Papadimitriou, skim chap. 4.
• Lecture 09: Wed, Feb 14. First-Order logic. Models and Interpretations. Tautologies and unsatisfiable sentences. Prenex Normal Form, Skolemization, Universal Formulas, Herbrand's Theorem. Read: Papadimitriou, beginning of chap. 5.
• No class Mon, Feb 19, President's day.
• Lecture 10: Wed, Feb 21 R.e. test for universal tautologies, undecidability of universal tautoligies (Church-Turing Theorem), compactness theorem, Lowenheim-Skolem theorem, axiomatizable theories and their recursive enumerability, Godel completeness theorem.Read: Papadimitriou, chap. 5.
• Lecture 11: Fri, Feb 23 (substitute for Mar. 19). (Un)decidability of specific models, model of number theory. Peano Arithmetic. Godel's incompleteness theorem and extensions. Limitations of First-Order Logic. Introduction to descriptive complexity. Wrap-Up of Logic. Problem Set 3 out (on logic, due Monday Mar. 5). Read: Sipser, sec. 6.2, Papadimitriou, chap. 6.
• Lecture 12: Mon, Feb 26. Time Complexity. Linear speedup. Universality of polynomial time. Class P, Examples of problems in P. Class NP, examples of problems in NP. P vs NP question.Read: Siser, sec 7.1-7.3, Papadimitriou, sec. 2.4.
• Lecture 13: Wed, Feb 28. Reductions and NP-Completeness. Cook-Levin Theorem. Examples of NP-complete problems. Read: Sipser, sec. 7.4-7.5, Papadimitriou, chap. 8-9.
• Lecture 14: Mon, Mar 05. More NP-complete problems. 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 (primality). Read: Papadimitriou, chap. 10.
• Lecture 15: Wed, Mar 07. More on NP intersection coNP. Primality in NP intersection coNP. Mincut/Maxflow theorem. Structure of NP-complete problems. Ways to deal woth NP-completeness: randomization, input restrcitions, average-case analysis and approximation algorithms. Examples of Approximation algorithms for NP-complete problems. Problem Set 4 out (on P, NP, NP-completeness, optimization problems, due Friday Mar. 28). Read: Papadimitriou, more chap. 10, 14.1-14.2, Sipser, sec. 10.1
• No classes Mar 12-16, spring break.
• No classes Mar 19-23, 2 substitute classes (Feb 23 and April 6).
• Lecture 16: Mon, Mar 26. Space Complexity. General relations between space and time. Reachability method. Savitch's theorem. Classes PSPACE and NPSPACE, their equality. NP in PSPACE. Read: Sipser, sec. 8.1-8.2, Papadimitriou, sec. 7.3
• Lecture 17: Wed, Mar 28. 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
• Lecture 18: Mon, Apr 02. Sublinear space model. Logarithmic space. Classes L and NL. Log-space reductions. NL-complete problems (REACHABILITY, 2SAT). NL = coNL. Problem Set 5 out (on space complexity, due Wednesday Apr. 11). Read: Papadimitriou, sec. 16.1, Sipser 8.4-8.5.
• No class on Wed, Apr 04. Substitute on Fri, Apr 20.
• Lecture 19: Fri, Apr 06. Related topics: (1) P-completeness (circuit value problem); (2) Oracle separations of P and NP; (3) time and space hierarchy theorems (as corollaries, separation of P and EXP, NL and PSPACE). Read: Sipser, end of sec. 10.5, sec. 9.1, 9.2, 9.3, Papdimitriou, sec. 7.2, 8.2, 14.3.
• Lecture 20: Mon, Apr 09. Randomized Computation and its importance. Class BPP. Aplification lemma for BPP. Randomized test for primality. Schwartz-Zippel lemma, randomized test for polynomial identity. Applications: (1) testing equivalence of read-once branching programs; (2) efficient communication protocol for testing string equality. Read: Sipser, sec. 10.2.
• Lecture 21: Wed, Apr 11. Other randomized complexity classes: PP, RP, coRP and ZPP. ZPP equals RP intersection coRP. Primality belongs to ZPP (sketch). Inadequacy of PP (NP belongs to PP). RP belongs to NP intersection BPP. Class P/poly (languages having non-uniform polynomial size circuits). RP belongs to P/poly. Ideas of random walk (randomized algorithm for 2SAT). Read: Papadimitriou, sec. 11.1, 11.2, 11.4.
• Lecture 22: Mon, Apr 16. BPP belongs to P/poly. Same result is unlikely for NP (see below). 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. Mention Toda's theorem: PH belongs to P^PP. Problem Set 6 out (on randomization and interactive protocols, due Wednesday Apr. 25). Read: Papadimitriou, sec. 11.4, 17.2.
• Lecture 23: Wed, Apr 18. 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)). Is randomness necessary? Derandomization techniques: (1) specific (method of conditional probabilities, example for MAX3SAT), (2) general (pseudorandom generators); (3) weaken the assumption of perfect unbiased randomness (imperfect random sources, von Newman trick, slightly 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). Read: Papadimitriou, Sec. 13.1 (example of MAX3SAT), 11.3, 16.3, Saks survey
• Lecture 24: Fri, Apr 20. Introduction to interactive protocols. Class IP, GNI example. Zero-knowledge, class PZK, GI example. Read: Sipser, Sec. 10.4, Papadimitriou, pp. 289-293, sec. 19.2, Goldreich's lectures
• Lecture 25: Mon, Apr 23. IP=PSPACE (Shamir's theorem). Arthur-Merlin games, class AM. Private coins = public coins: IP(r) belongs to AM(r+2). Collapse theorem: AM(r) belongs to AM(r/2). Universality of AM. Multiple provers, class MIP. MIP=NEXP. coNP in AM implies the hierarchy collapses. Read: Sipser, sec. 10.4, Papadimitriou, pp. 474-480, pp. 506-508, lecture notes, Goldreich lectures
• Lecture 26: Wed, Apr 25. Refereed games and conflicting provers (class RG). RG=EXP. Rounds and private/public coins: RG(1,private) = PSPACE = RG(poly,public). Oracles vs. provers, class PCP. PCP=MIP=NEXP. Property testing using oracles. PCP-characterization of NP: NP=PCP(O(log n), O(1)). Applications to inapproximability. Read: Papadimitriou, sec. 13.3, lecture notes, Goldrecih's lectures, Feige/Kilian paper
• Lecture 27: Mon, Apr 30. Cryptography and complexity. Basic primitives: one-way functions/permutations, trapdoor functions/permutations. Examples (multiplication, modular exponentiation, RSA). Why P<>NP is necessary but not sufficient for cryptography (e.g., one-way functions). Read: Sipser, sec. 10.6, Papadimitriou, chap. 12

Back to the course page