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

**Topics: (will be updated soon)**

- (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
)

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