Alexander Sherstov

Associate Professor
Computer Science Department
UCLA

 

I am thrilled to be the winner of 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. Recent offerings: Spring 2013Spring 2014Spring 2015Fall 2015Fall 2016Fall 2017

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. Recent offerings: Spring 2012Winter 2013Winter 2014Winter 2016Spring 2017

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. Recent offerings: Winter 2012Fall 2013Fall 2014Spring 2016