Alexander Sherstov

Associate Professor
Computer Science Department
UCLA

 

I am thrilled to be a winner of the 2021 campus-wide Distinguished Teaching Award, which is UCLA's highest honor for excellence in the classroom. 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

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 2012Winter 2013Winter 2014Winter 2016Spring 2017Winter 2018Winter 2019Fall 2020

CS289 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 2012Fall 2013Fall 2014Spring 2016Spring 2018Spring 2019Winter 2021