15-252: More Great Ideas in Theoretical Computer Science, Spring 2021
Lectures: Thursday 08:30PM - 09:20PM EDT (remote)
Instructors: Venkatesan Guruswami (venkatg@cs.cmu.edu)
Teaching Assistant: Andrii Riazanov (riazanov@cs.cmu.edu)
Office Hours: Venkat: Friday 10:00AM EDT, Andrii: Wednesday 9:30PM EDT
Piazza Link: Here.
Course description:
This 5-unit mini-course is intended for students who are taking 15-251 and would like more intensive exposure to theoretical computer science. The class meets once a week for a lecture and the students are expected to solve a number of homework problems during the course of the semester. The work done in 15-252 does not replace any of the requirements of 15-251.
Lecture topics and notes
Lecture topics and notes will appear here (the YouTube video links will be posted on Piazza). In the meanwhile, here is last year's page, which will give a pretty good idea of the topics we plan to cover.
- (Feb 4):
Sorting Pancakes
(Notes,
Slides
)
- (Feb 11):
Nondeterministic finite automata
(Lecture transcript)
- (Feb 18):
Lambda Calculus
(Video Part 1,
Video Part 2,
Slides,
Frank Pfenning's notes
)
- (Feb 25):
Kolmogorov complexity (Lecture transcript, Lecture notes)
- (Mar 4):
Communication complexity (Lecture transcript, Some notes)
- (Mar 11):
Fast integer and polynomial multiplication via FFT (Lecture transcript, Some notes, External slides )
- (Mar 18):
Spectral Graph Theory (Lecture transcript; Notes from last year (which works with the Laplacian instead of adjacency matrix))
- (Mar 25):
Linear Programming (Lecture transcript)
- (Apr 1):
PCPs for NP and approximation hardness (Lecture transcript, Notes)
- (Apr 8):
Probabilistic Method (Lecture transcript, Notes)
- (Apr 22):
Pseudorandomness (Lecture transcript, Notes)
- (Apr 29):
Fast exponential algorithms for 3SAT (Lecture transcript, Lecture notes from 15-210)
- (May 6): Open Q&A; Error-correcting bit flips ((MIni)-lecture transcript; Introductory notes (from CMU coding theory class))
Assignments
General rules: There will be a short homework assigned every week. The homeworks will usually go out on Fridays and be due by midnight the next Friday. They must be submitted via Gradescope. You can work alone or with one other person (the recommended option is the latter). However you must write the solutions completely by yourself. You may not share any written documents. Submissions of legible handwrittings is allowed, although LaTeXing is preferred.
- Problem Set 1, due Feb 12
- Problem Set 2, due Feb 19
- Problem Set 3, due Feb 26
- Problem Set 4, due March 5
- Problem Set 5, due March 12
- Problem Set 6, due March 19
- Problem Set 7, due March 26
- Problem Set 8, due April 3
- Problem Set 9, due April 10
- Problem Set 10, due April 21
- Problem Set 11, due April 30
- Problem Set 12, due May 7
Evaluation
Attendance and weekly assigned problems.