--- title: Great Theory Hits --- # Raghu Meka: CS289: Great Theory Hits of 21st Century Winter 2021 | [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. Lectures: Monday/Wednesday 10-11:50. [On Zoom and will be recorded](https://ucla.zoom.us/j/98304070079). Office hours are by appointment (quite flexible). --- ## Course Work We will have three take-home midterms worth 30% each. - Midterm 1:January 25. Due in 24 hours. - Midterm 2: February 17. Due in 24 hours. - Midterm 3: March 11th. Due in 24 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 access them here: - [Scribble link for part 1](https://scribbletogether.com/whiteboard/76CFCEE4-A041-4921-91D5-4D14D3EF4E8A). [PDF for part 1](https://www.dropbox.com/s/ttvlryybiaezbds/GreatHits%20Part%201.pdf?dl=0) - [Scribble link for part 2](https://scribbletogether.com/whiteboard/28252C1B-4005-40A3-B4B9-4E36E91E0DA8). [Pdf is here](https://www.dropbox.com/s/36oaw9tjf0re1ph/GreatHitsPart2.pdf?dl=0). - [Vibe canvas link for part 3](https://app.vibe.us/folder.ixx-V3ElFhPc1Vov2CjU3O/XNTQ4rw_MdOS6hbeIUt-mi/KYJzIfKobmkaDq2pU9T2H4) - [Vibe canvas link for part 4](https://app.vibe.us/smart.ALL_BOARDS/-CrL_nx7fT-p34V-1tZRhg/00Qm1o69uqF6TRbeOFfscC) - [Vibe canvas link for part 5](https://app.vibe.us/smart.ALL_BOARDS/AgYVL9AcGfURiwIm61X4D3/kqIWFK_Hy25FnroMdkO3pE) We will also use Campuswire to ask and answer questions about the class. The link for registering is [here](https://campuswire.com/p/G56F93947). --- ## 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)
Last changed by  
 
Raghu Meka
917

Read more

Algorithmic Machine Learning

In this course we will look at a handful of ubiquitous algorithms in machine learning. We will cover several classical tools in machine learning but more emphasis will be given to recent advances and developing efficient and provable algorithms for learning tasks. A tentative syllabus/schedule can be found below; the topics may change based on student interests as well. You can also check last year's course notes for a more details about what's to come.

4/24/2024
Research

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.

2/29/2024
Algorithmic Machine Learning

In this course we will look at a handful of ubiquitous algorithms in machine learning. We will cover several classical tools in machine learning but more emphasis will be given to recent advances and developing efficient and provable algorithms for learning tasks. A tentative syllabus/schedule can be found below; the topics may change based on student interests as well. You can also check last year's course notes for a more details about what's to come.

2/23/2024
Teaching

Here are the courses I have taught or will in the future.

2/23/2024
Read more from Raghu Meka
Published on HackMD