The Taub Faculty of Computer Science Events and Talks

In the 'frequent items' problem one sees a sequence of items in a stream (e.g. a stream of words coming into a search query engine like Google) and wants to report a small list of items containing all frequent items. In the 'change detection' problem one sees two streams, say one from yesterday and one from today, and wants to report a small list of items containing all those whose frequencies changed significantly. For both of these problems, we would like algorithms that use memory substantially sublinear in the length of the stream. We describe new state-of-the-art solutions to both problems. For the former, we make use of chaining methods to control the suprema of Rademacher processes to develop an algorithm BPTree with provably near-optimal memory consumption. For the latter, we develop the first algorithm to simultaneously achieve asymptotically optimal space, fast query and update time, and high success probability (over the random coins flipped bythe algorithm) by reducing the problem to a certain graph partitioning problem, which we then give a new algorithm for. Based on joint works with Vladimir Braverman, Stephen Chestnut, Nikita Ivkin, Kasper Green Larsen, Huy Le Nguyen, Mikkel Thorup, Zhengyu Wang, and David P. Woodruff.

Bio:
Jelani Nelson is a Professor of Electrical Engineering and Computer Science at the University of California, Berkeley. He won the 2014 Presidential Early Career Award for Scientists and Engineers. Nelson is the creator of AddisCoder, a computer science summer program for Ethiopian high school students in Addis Ababa.

Prof. Nelson is from St. Thomas, U.S. Virgin Islands. He studied mathematics and computer science at the Massachusetts Institute of Technology and remained there to complete his doctoral studies in computer science. His Master's dissertation, External-Memory Search Trees with Fast Insertions, was supervised by Bradley C. Kuszmaul and Charles E. Leiserson. He was a member of the theory of computation group, working on efficient algorithms for massive datasets. His doctoral dissertation, Sketching and Streaming High-Dimensional Vectors, was supervised by Erik Demaine and Piotr Indyk.

After his doctorate, Prof. Nelson worked as a postdoctoral scholar at the Mathematical Sciences Research Institute in Berkeley, California, then Princeton University and the Institute for Advanced Study. He specializes in sketching and streaming algorithms.