Description
Meet: Tuesday & Friday 1:35 - 3:15 pm (Zoom)
https://northeastern.zoom.us/j/99217297716
Office hours: by appointment
Grading: Grades will be based on problem sets (expect about 6), and a group presentation on advanced topics in complexity theory. Problem sets must be typed using latex and submitted as a PDF using gradescope. The breakdown is 60% problem sets, 30% group presentation, 10% class participation.
Problem Set Policies: Collaborating with other students in the class on homework problems is fine and encouraged, though we urge you to attempt working out all of the problems by yourself first. In any case, you must write up your solutions, in your own words. Furthermore, if you did collaborate on any problem, you must clearly list all of the collaborators in your submission. Finding solutions to homework problems on the web, or by asking students not enrolled in the class is strictly prohibited.
Textbooks
1. Sipser 3rd Ed: Introduction to the Theory of Computation
2. Arora and Barak: Computational Complexity
Latex Resources
You should prepare your homework solutions using LaTeX, and submit PDFs to Gradescope. LaTeX is a scientific document preparation system; most CS technical publications are prepared using this tool. Great editors exist on most platforms. Some recommend TexShop for Mac. TeXstudio is a good cross-platform editor.
The not so short introduction to Latex (https://tobi.oetiker.ch/lshort/lshort.pdf) is a good reference to get you started.
Previous Year's Course
https://www.ccs.neu.edu/home/hlnguyen/cs7805/spring20/schedule.html
https://northeastern.zoom.us/j/99217297716
Office hours: by appointment
Grading: Grades will be based on problem sets (expect about 6), and a group presentation on advanced topics in complexity theory. Problem sets must be typed using latex and submitted as a PDF using gradescope. The breakdown is 60% problem sets, 30% group presentation, 10% class participation.
Problem Set Policies: Collaborating with other students in the class on homework problems is fine and encouraged, though we urge you to attempt working out all of the problems by yourself first. In any case, you must write up your solutions, in your own words. Furthermore, if you did collaborate on any problem, you must clearly list all of the collaborators in your submission. Finding solutions to homework problems on the web, or by asking students not enrolled in the class is strictly prohibited.
Textbooks
1. Sipser 3rd Ed: Introduction to the Theory of Computation
2. Arora and Barak: Computational Complexity
Latex Resources
You should prepare your homework solutions using LaTeX, and submit PDFs to Gradescope. LaTeX is a scientific document preparation system; most CS technical publications are prepared using this tool. Great editors exist on most platforms. Some recommend TexShop for Mac. TeXstudio is a good cross-platform editor.
The not so short introduction to Latex (https://tobi.oetiker.ch/lshort/lshort.pdf) is a good reference to get you started.
Previous Year's Course
https://www.ccs.neu.edu/home/hlnguyen/cs7805/spring20/schedule.html
General Information
1/19: Introduction, math background. Sipser 1-24
Review of math background. Skim Sipser to make sure this is all familiar to you.
1/22: Finite automata. Sipser 31-54
DFA, NFA, closure properties of regular languages
1/26. Equivalence of NFA, DFA, Regular Expressions. Sipser 54- 77.
Started pumping lemma.
1/29: Pumping Lemma and 2-Way DFAs. Sipser 77-82 and notes below
2/2: Turing Machines. Sipser 165-187
2/5: Church-Turing Thesis. Start Undecidability. Sipser 201-207
2/9: Undecidability. Sipser 207 - 209 and 215- 220
2/12: Undecidability of Number Theory, Godel's incompleteness. Sipser 252-259
See https://files.boazbarak.org/introtcs/lec_09_godel.pdf
Optional topic: Read Sipser 227-233 for another simple-to-state undecidable problem.
Optional topic: Read Sipser 227-233 for another simple-to-state undecidable problem.
2/16: Rice's Theorem, Unrecognizability, Kolmogorov Complexity
Sipser pages 209-210, 238, 261-269
2/19: P vs NP
Sipser pages 275 - 298
2/23: NP-Completeness, Reductions
Sipser 299-304 and 320-322
2/26: Cook-Levin Theorem
Sipser 304-310 or Arora-Barak 44-50
Arora-Barak 54-55 (decission vs search)
Arora-Barak 54-55 (decission vs search)
3/2: More NP-completeness, coNP, EXP, NEXP
Sipser 314-319
Arora-Barak: 55- 62
Arora-Barak: 55- 62
3/5: Diagonalization: Time-Hierarchy, Ladner's Theorem
Arora-Barak: 68-72
3/9: Finish Ladner's Theorem, Relativization
Arora-Barak 72-76
3/12: Space Complexity
Arora-Barak 78-87
3/16: Polynomial Hierarchy
Arora-Barak 95-99, 102-103
3/19: Circuits
Arora-Barak 106-110, 112 (bottom) - 114 (top). 115-116
3/23: Circuit lower bounds
https://people.seas.harvard.edu/~salil/cs221/fall02/scribenotes/nov18.pdf
see also:
https://homes.cs.washington.edu/~anuprao/pubs/CSE531Sp2020/lecture16.pdf
and Chatper 14 of Arora-Barak
see also:
https://homes.cs.washington.edu/~anuprao/pubs/CSE531Sp2020/lecture16.pdf
and Chatper 14 of Arora-Barak
3/26: Randomized Computation
Arora-Barak 123- 138
3/30: Cryptography
Arora-Barak 172-180
4/2: Cryptography continued
Arora-Barak 180-186, 189-191, 369-370
See also http://www.ccs.neu.edu/home/wichs/class/crypto-fall15/lecture7.pdf, http://www.ccs.neu.edu/home/wichs/class/crypto-fall15/lecture8.pdf for hard-core bit of one-way permutation.
See also http://www.ccs.neu.edu/home/wichs/class/crypto-fall15/lecture7.pdf, http://www.ccs.neu.edu/home/wichs/class/crypto-fall15/lecture8.pdf for hard-core bit of one-way permutation.
4/6: Interactive Proofs
Arora-Barak 143-151, 157-162
4/9: Zero Knowledge, PCP
Arora-Barak 186-188, 237-254
| Name | Office Hours | |
|---|---|---|
Daniel Wichs | When? Where? |