✳flâneur — a map of the web's best reading

15-855: Graduate Computational Complexity Theory, Fall 2017

cs.cmu.edu · 1,179 words · saved by 1 readers

Prerequisite: An undergraduate course in computational complexity theory, covering most of "Part III" of Sipser and/or most of Carnegie Mellon's 15-455. Potential topics: Models and Time Hierarchy Theorem. Nondeterminism, padding, Hopcroft-Paul-Valiant Theorem. Circuits and advice. Randomized classes. Cook-Levin Theorem and SAT. Nondeterministic Time Hierarchy Theorem, and nondeterministic models. Oracles, alternation, and the Polynomial Time Hierarchy. Kannan's Theorem, Karp-Lipton, and PH vs. constant-depth circuits. Time-Space tradeoffs for SAT. Randomized classes vs. PH. Interactive proofs and the AM hierarchy. NP in BPP implies PH in BPP, and Boppana-Hastad-Zachos. BCGKT Theorem and Cai's Theorem. Counting classes and the permanent. Valiant's Theorem. Algebraic Complexity. IP = PSPACE and interactive proofs. Instance checkers and Santhanam's Theorem. Random restrictions and AC0 lower bounds for parity. Monotone circuit lower bounds. Razborov-Smolensky lower bounds for AC0[p]. Vali

15-855: Graduate Computational Complexity Theory, Fall 2017 15-855: Graduate Computational Complexity Theory, Fall 2017 Meeting time and place: Tuesday and Thursday, 10:30am-11:50am, GHC 4303. Course bulletin board: Piazza . This will be used for all course-related communications. Course grading: Gradescope . Course entry code: M3YGWX Instructor: Ryan O'Donnell (Office Hours: Fri. 3:30-4:30, GHC7213) TAs: Ellis Hershkowitz (Office Hours: Mon. 1:00-3:00, GHC9219), Nicolas Resch (Office Hours: Sun. 3:00-4:00, GHC7507) Textbook: Computational Complexity: A Modern Approach , by Arora and Barak. Ha

Explore this link on the map →

saved by

related reading