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.
Resources: There is no required course text and we will often refer to the original papers for source material.
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)
: 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.