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.

Course work: We will have two assignments worth 50% each. These essentially serve as take-home mid-term and final respectively.

Hours & Location: MW 2-3:50, Bunche Hall 1265. Office hours: Wednesday 10:30 - 11:30, BH 3732H.

The following is a tentative (can be adjusted according to student interests) list of topics to be covered.
Zig-Zag Product and SL = L (3 lectures)
QIP = PSPACE (2 lectures)
Unique Games Conjecture and Hardness of Approximation (3 lectures)
Extended Formulations, LP/SDP Relaxations, and Communication Complexity (3 lectures)
Laplacian Solvers and Graph Sparsification (3 lectures)
Homomorphic Encryption (2 lectures)
Constructive Lovasz Local Lemma (2 lectures)
Constructive Discrepancy Minimization (2 lectures)


Assignment submission: We will use Gradescope for assignments and they have to be submitted by 10PM on their due date. This is extremely helpful both for me as well as for you - you'll get better feedback and will have a digital record of all your assignments that you can refer to later. Things to keep in mind: 1) Within two weeks of the course, you should receive a registration link from Gradescope. If you don't receive it before the first homework, contact me immediately; this will give you access to the website. 2) Watch this one-minute video with complete instructions. Follow them to the letter! The simple guidelines make the process considerably smoother. 3) Make sure you start each problem of an assignment on a new page. 4) To generate a PDF scan of the assignments, you can follow the instructions here; you can also use the scanners in the library.

Resources: There is no required course text and we will often refer to the original papers for source material.



Academic honesty: The students are expected to fully abide by UCLA's student conduct policies, including Section 102.01 on academic honesty. You will find a wealth of helpful materials here, including the Student Guide to Academic Integrity. Academic dishonesty will be promptly reported to the Dean of Students' Office for adjudication and disciplinary action. Remember, cheating will have significant and irrevocable consequences for your academic record and professional future. Please don't cheat.

While collaboration with other students on assignments is fine, you should clearly mention the collaborators. You should make your own slides and when you use content from another source, you should explicitly state so. Under no circumstances may you use code directly from resources on the web without explicitly citing the source.