---
title: Great Theory Hits
---
# Raghu Meka: CS289: Great Theory Hits of 21st Century Winter 2023
| [HOME](http://www.raghumeka.org) | [RESEARCH](http://raghumeka.github.io/research.html) | [TEACHING](http://raghumeka.github.io/courses.html) |
| -------- | -------- | -------- |
---
## Introduction
We will cover a handful of groundbreaking results across the entire gamut of theoretical computer science discovered in the 21st century! A tentative list of topics can be found below; the topics may change based on student interest as well.
**Prerequisites**: You **need** background in linear algebra, probability theory, and algorithms (all at a typical undergraduate upper-division level) to make the class fun and interesting for you as well as for me. You can also check last years' [notes](https://hackmd.io/F_qqEjKqTxS3S2_JYZrurg) to get an idea.
Undergrads are welcome! I will allow PTEs as long as you can assure yourself that you have the prerequisites. If in doubt, please contact me by email.
**Lectures: M-W 10-11:50. BOELTER 5422**. Office hours are by appointment (quite flexible).
---
## Course Work
We will have three take-home midterms worth 30% each.
- Midterm 1: February 1. Due in 48 hours.
- Midterm 2: February 27. Due in 48 hours.
- Midterm 3: March 20th. Due in 48 hours.
10% credit is for class participation (asking questions in class). If you can't attend class live, then talk to me and we will figure out a suitable fix.
The best resources will be the original papers. The transcipt of the lectures will be available on Scribble. You can also access last year's notes (and other details) on previous years' course webpage [here](https://hackmd.io/F_qqEjKqTxS3S2_JYZrurg).
---
## Syllabus
The syllabus is flexible and we can cover diverse topics based on your interest. The following is a tentative list of topics to be covered. For each of the specific results, we will use it as an excuse to learn some essential tools in theory of computing.
- SL = L: Undirected connectivity in Logspace (4 lectures). Refs: [This chapter](https://people.seas.harvard.edu/~salil/pseudorandomness/expanders.pdf) and [the original paper](https://omereingold.files.wordpress.com/2014/10/sl.pdf). This excellent (and award winning) survey on [expander graphs](https://www.ams.org/journals/bull/2006-43-04/S0273-0979-06-01126-8/) for further topics.
- Graph Sparsification and interlacing Polynomials (4 lectures). The original [paper](https://arxiv.org/abs/0808.0163). [These slides and videos](https://simons.berkeley.edu/talks/graph-sparsification) by Nikhil Srivastava. Our presentation will be similar but we will skip some parts and expand on others.
- LP/SDP Relaxations: Extended Formulations and Communication Complexity (4 lectures)
- Sensitivity conjecture (2 lectures)
- Improved bounds on sunflower conjecture (2 lectures)
- Logconcave polynomials, mixing in matroids (4 lectures)/Quantum Testing (4 lectures)

CS181: Introduction to Theoretical Computer Science Fall 2022 HOME RESEARCH TEACHING Introduction The official title for the course is Formal Languages and Automata Theory. This offering will be geared towards introducing you to the beautiful and profundly impactful world of Theoretical Computer Science (TOC). The following three questions encompass our main learning goals: :::spoiler 1. What is computation?

11/29/2022Raghu Meka HOME RESEARCH TEACHING Here are the courses I have taught or will in the future. CS181: Introduction to Formal Languages and Automata Theory Fall 2022, Fall 2021, Fall 2020

11/12/2022Raghu Meka: CS289: Great Theory Hits of 21st Century Winter 2021 HOME RESEARCH TEACHING Introduction We will cover a handful of groundbreaking results across the entire gamut of theoretical computer science discovered in the 21st century! A tentative list of topics can be found below; the topics may change based on student interest as well. Prerequisites: You need background in linear algebra, probability theory, and algorithms (all at a typical undergraduate upper-division level) to make the class fun and interesting for you as well as for me.

11/12/2022Raghu Meka HOME RESEARCH TEACHING My main interests are in complexity theory, learning theory, algorithm design. More generally, I like probability and combinatorics related things. The best resource for up to date publications really is to look up my profile on Google scholar. Publications

10/26/2022
Published on ** HackMD**