--- 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. Check your prerequisites by testing yourself with these problems [assignment](https://ucla.box.com/s/zra5139k5625a68g09anv7jkfjnc7y4r). 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). [Zoom link](https://ucla.zoom.us/j/93361419541). (Zoom interactions won't count toward class participation.) **edStem:** We will use edStem for communication and announcements (including for links to video recordings) - please register [here](https://edstem.org/us/join/V6qgdE). --- ## 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). --- ## Notes :::spoiler **Course notes**: We will use [ScribbleTogether](https://scribbletogether.com/). - Note that each lecture is on a different sheet within the files. - [Notes on extension complexity](https://scribbletogether.com/whiteboard/6C452FDF-4AE9-47C4-9589-8431B27B39EA) - [Notes on information complexity](https://scribbletogether.com/whiteboard/9E530A3D-95EC-4C29-A34C-C9676BD36FFE) - [Notes for Sunflower](https://scribbletogether.com/whiteboard/A355971E-3A0D-4776-9E0B-DD9A81B7E5D7). - [Notes for Parts 1, 2](https://scribbletogether.com/whiteboard/7BD725CA-A417-4CD0-92DE-78C3304FC58B). --- ## 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. - Sensitivity conjecture (2 lectures) - Improved bounds on sunflower conjecture (3 lectures) - Information Complexity and Applications (4 lectures) - Quantum LDPC Codes (5 lectures)
Last changed by  
 
Raghu Meka
3601

Read more

Algorithmic Machine Learning

HOME RESEARCH TEACHING Introduction 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. Make sure you can answer the questions in Assignment 0 for yourselves before registering for the course. Coursework

6/7/2023
Research

Raghu 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 On User-Level Private Convex Optimization ICML 2023

5/16/2023
Teaching

Raghu 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 CS180: Algorithms and Complexity

3/27/2023
Algorithmic Machine Learningn Spring 2023

HOME RESEARCH TEACHING Introduction 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. Coursework There will be four assignments for the course that will cover 70% of the credit and a final that will cover 25% of the credit; 5% is for class participation (live-class participation and/or extensive contributions to online discussions). Each assignment will have both written as well as programming components. We'll predominantly use gradescope for the assignments. The final will be online on gradescope (and will be released as per university schedule). You could potentially discuss how to solve problems with others specifically (a better option would be to just ask questions openly on edStem) but see course policies below and make sure you do not violate them.

2/24/2023
Read more from Raghu Meka
Published on HackMD