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.

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)

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.