CS 172 Computability and Complexity

Prof. Luca Trevisan

Spring 2015
Tuesdays and  Thursdays 2:00-3:30pm
306 Soda

News

 

Textbook

Note: this book is very good but also very expensive. If you can find a cheap used 1st or 2nd edition, go for it.

 

Information

 

Work

 

Lectures

So far:

  Topic Readings Problem sets
1: January 20 Summary of the course Chapter 0 .
2: January 22 Deterministic Finite Automata Section 1.1 Homework 1 out
3: January 27 Nondeterministic finite automata Section 1.2 .
4: January 29 Equivalence of regular expression and finite automata Section 1.3 Homework 2 out
5: February 3 Myhill-Nerode theorem Handout 1  
6: February 5 State minimization  Handout 1 Homework 3 out
7: February 10 Streaming algorithms Handout 2  
8: February 12 Turing machines Chapter 3
Turing's paper		 Homework 4 out
9: February 17 Variants of Turing machines, non-determinism, enumerators Chapter 3
10: February 19 Halting problem Chapter 4 Practice Midterm
11: February 24 More decidability and undecidability results Chapter 4
February 26 MIDTERM I   Homework 5 out
12: March 3 Reducibility, Rice's theorem, and more undecidability results Sections 5.1, 5.3, Handout 3
13: March 5 Godel's incompleteness theorem Handout 4 Homework 6 out
14: March 10 Kolmogorov complexity Section 6.4, Handout 5
15: March 12 The classes P and NP Sections 7.1, 7.2, 7.3 Homework 7 out
16: March 17 Boolean circuits Section 9.3
17: March 19 NP-completeness of SAT Sections 7.4, 9.3 Homework 8 out
18: March 31 More NP-complete problems Handout 6
19: April 2 More NP-complete problems Handout 6 Practice midterm
20: April 7 NL-completeness Sections 8.2, 8.5
April 9 MIDTERM II   Homework 9 out
21: April 14 Savitch's theorem, NL=coNL Sections 8.4, Handout 7
22: April 16 PSPACE-completeness, hierarchy theorem Sections 8.3, 9.1, Handout 8 Homework 10 out
23: April 21 Zero knowledge proofs Handout 9, Handout 10
24: April 23 More on Zero knowledge proofs Handout 9, Handout 10 Homework 11 out
25: April 28 The PCP Theorem Handout 11
26: April 30 Complexity of Approximation Handout 11 Practice Final


The plan:

 
 
 
  Topic Readings Problem sets
1: January 20 Summary of the course, Finite Automata Chapter 0, Section 1.1 .
2: January 22 Non-deterministic automata, Regular expression Section 1.2 Homework 1 out
3: January 27 Equivalence of regular expression and finite automata Section 1.3 .
4: January 29 Equivalence of regular expression and finite automata Section 1.3 Homework 2 out
5: February 3 Myhill-Nerode theorem Handout 1  
6: February 5 State minimization  Handout 1 Homework 3 out
7: February 10 Streaming algorithms Handout 2  
8: February 12 Turing machines Chapter 3
Turing's paper		 Homework 4 out
9: February 17 Examples of Turing machines Chapter 3  
10: February 19 Variants of Turing machines, non-determinism, enumerators Chapter 3 Practice Midterm
11: February 24 Decidability, Halting problem Chapter 4
February 26 MIDTERM I   Homework 5 out
12: March 3 Reducibility and more undecidability Sections 5.1, 5.3
13: March 5 Rice's theorem and more undecidability Handout 3 Homework 6 out
14: March 10 Godel's incompleteness theorem Handout 4
15: March 12 Kolmogorov complexity Section 6.4, Handout 5 Homework 7 out
16: March 17 The classes P and NP Sections 7.1, 7.2, 7.3
17: March 19 Boolean circuits Section 9.3 Homework 8 out
18: March 31 NP-completeness of SAT Sections 7.4, 9.3
19: April 2 More NP-complete problems Handout 6 Practice midterm
20: April 7 More NP-complete problems Handout 6
April 9 MIDTERM II   Homework 9 out
21: April 14 NL, Savitch's theorem Sections 8.2, 8.4
22: April 16 NL-completeness Section 8.5 Homework 10 out
23: April 21 NL=coNL Handout 7
24: April 23 Hierarchy theorems Section 9.1
Handout 8		 Homework 11 out
25: April 28 Zero knowledge and cryptography Handout 9 .
26:April 30 Zero knowledge and cryptography Handout 9 Practice final
27: May 5 Zero knowledge and cryptography Handout 9  
27: May 7 Review