**15-252: More Great Ideas in Theoretical Computer Science**

**Lectures**: Thursday 18:30 - 19:20 in GHC 4215

**Instructors**: Venkatesan Guruswami (venkatg@cs.cmu.edu)

**Teaching Assistant:** Sai Sandeep (spallerl@andrew.cmu.edu)

**Office Hours**: Venkat: Thursday 11AM-12PM (GHC 7211), Sai: Friday 11AM-12PM (GHC 9005)

**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**

- (01/16):
Sorting Pancakes
(Notes,
Slides
)
- (01/23):
Non-deterministic Finite Automata
(Notes,
Online Slides
)
- (01/30):
Lambda Calculus
(Video Part 1,
Video Part 2,
Slides,
Frank Pfenning's notes
)
- (02/06):
Kolmogorov Complexity
(Notes
)
- (02/13):
Fast Integer Multiplication
(Notes
)
- (02/20):
Spectral Graph Theory
(Notes
)
- (02/27):
Matchings and Determinants
(Notes
)
- (03/05):
Constraint Satisfaction Problems
(Notes
)
- (03/19):
Probabilistically Checkable Proofs
(Notes, Lecture transcript, Recording, Chat Transcript
)
- (03/26):
Probabilistic Method
(Notes, Lecture transcript, Recording
)
- (04/02):
Expander Graphs
(Notes, Lecture transcript, Recording
)
- (04/09):
Reed-Solomon Codes
(Lecture Transcript, Recording, Essential Coding Theory Book (See chapters 1.1,1.2,5.1,5.2,15.1), Online Lecture Notes on Error Correcting Codes
)
- (04/23):
Pseudorandomness: Hardness vs. Randomness
(Notes, Recording, Lecture Transcript
)
- (04/30): Exponential time algorithms
(Lecture notes from 15-210, Online Notes on Fast exponential time algorithms, Recording, Lecture Transcript
)

**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. 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. Solutions must be typeset using LaTeX.

**Evaluation **

Attendance and weekly assigned problems.