I am thrilled to be a winner of the 2021 campus-wide Distinguished Teaching Award, which is UCLA's highest honor for excellence in teaching. Previously, I won the 2014 Northrop Grumman Excellence in Teaching Award, presented annually to a faculty member of UCLA's School of Engineering.
I annually teach both undergraduate and graduate courses in theoretical computer science. My current and past course offerings are as follows.
CS181 Formal Languages and Automata Theory
This course is an undergraduate introduction to the theory of computation. We
will study a variety of abstract computational devices, from very simple and
limited to highly sophisticated and powerful: deterministic and
nondeterministic finite automata, regular expressions, pushdown automata,
context-free grammars, and Turing machines. We will completely characterize the
relative computational capabilities of these devices. Lastly, we will discover
that there are important practical problems that cannot be solved by any
computational device at all.
My recent offerings:
Spring 2013
•
Spring 2014
•
Spring 2015
•
Fall 2015
•
Fall 2016
•
Fall 2017
•
Fall 2018
•
Fall 2019
•
Winter 2020
•
Spring 2022
CS281 Computability and Complexity
Computers have become faster over the decades. Computations that were
infeasible fifty years ago now take a split second. However, many natural and
practically significant computational problems will always remain off limits.
Computational complexity is a branch of discrete mathematics that studies the
fundamental limitations to efficient computation. A variety of resources other
than time can be used to quantify efficiency, such as memory and randomness.
Computational complexity theory studies these resources in a unified, clean,
and abstract way. This graduate course will cover many of the field's
celebrated discoveries and outline current research frontiers. Tentative
topics include NP-completeness, diagonalization, oracle computations, space
complexity, Turing machines with alternating quantifies, Boolean circuits and
circuit lower bounds, randomized computation, interactive proofs,
derandomization, pseudorandom constructions, and probabilistically checkable
proofs.
My recent offerings:
Spring 2012
•
Winter 2013
•
Winter 2014
•
Winter 2016
•
Spring 2017
•
Winter 2018
•
Winter 2019
•
Fall 2020
•
Winter 2022
•
Winter 2023
•
Winter 2024
CS289/CS285CC Communication Complexity
Consider a function f whose arguments are
distributed among several parties, making it impossible
for any one party to compute f in isolation.
Communication complexity theory studies how many
bits of communication are needed to evaluate f.
A trivial approach is for the parties to communicate their inputs to each
other. While this costly solution is optimal in some cases, one can often
accomplish the task with surprisingly little communication. To cite a famous
example, one can check with accuracy 99% if two geographically separated
databases are identical by communicating only eight bits, regardless of
how large the databases actually are.
Over the past three decades, communication complexity
has evolved into a central area of theoretical computer
science, with deep open questions, beautiful
mathematics, and many applications. This graduate
course is a self-contained introduction to
communication complexity, with coverage of the
fundamentals, key classic theorems, and current research
directions.
My recent offerings:
Winter 2012
•
Fall 2013
•
Fall 2014
•
Spring 2016
•
Spring 2018
•
Spring 2019
•
Winter 2021
•
Fall 2022
•
Fall 2023
•
Fall 2024