# Stochastics and Statistics Seminar

## Optimal lower bounds for universal relation, and for samplers and finding duplicates in streams

**Speaker Name:**
Jelani Nelson (Harvard University)

**Date:**
September 29, 2017

**Time:**
11:00am

**Location:**
E18-304

**Abstract:**

Consider the following problem: we monitor a sequence of edge

insertions and deletions in a graph on n vertices, so there are N = (n

choose 2) possible edges (e.g. monitoring a stream of friend

accepts/removals on Facebook). At any point someone may say "query()",

at which point must output a random edge that exists in the graph at

that time from a distribution that is statistically close to uniform.

More specifically, with probability p our edge should come from a

distribution close to uniform, and with probability 1-p our sampler

can do anything (i.e. it can say "Fail", or output a non-existent

edge). The primary goal is to design an algorithm that uses very

little memory. Whereas the trivial solution maintains N bits, keeping

track of which edges currently exist, we show that the optimal space

complexity for this problem is Theta(min{N, log(1/p) * log^2(2 + N /

log(1/p))}) bits. The upper bound follows by a very minor modification

of previous work, whereas the lower bound is our main novel

contribution.

This is joint work with Michael Kapralov (EPFL), Jakub Pachocki

(OpenAI), Zhengyu Wang (Harvard), David P. Woodruff (IBM Almaden), and

Mobin Yahyazadeh (Sharif).

**Speaker Bio:**

Jelani Nelson is Associate Professor of Computer Science at Harvard.

His main research interest is in algorithm design and analysis, with

recent focus on streaming algorithms, dimensionality reduction,

compressed sensing, and randomized linear algebra algorithms. He

completed his Ph.D. in computer science at MIT in 2011, receiving the

George M. Sprowls Award for best computer science doctoral

dissertations at MIT. He is the recipient of an NSF CAREER Award, ONR

Young Investigator Award, ONR Director of Research Early Career Award,

Alfred P. Sloan Research Fellowship, and Presidential Early Career

Award for Scientists and Engineers (PECASE).