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.



Transcript1 and Transcript2 for the class.

Assignemnt 1. Due Feb 26 6PM.

Assignment 2. Due March 26 6PM.

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: Wed 10:30 - 11:30; Engineering VI, Room 463.

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)
Two-Source Extractors (2 lectures)
LP/SDP Relaxations (Extended Formulations) and Communication Complexity (3 lectures)
Laplacian Solvers, Graph Sparsification, Interlacing Polynomials (4 lectures)
Homomorphic Encryption (2 lectures)
Constructive Lovasz Local Lemma (2 lectures)
Constructive Discrepancy Minimization (2 lectures)


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.