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