Huacheng Yu, Princeton University

Abstract

Motivated by storage applications, we study the following data

structure problem: An encoder wishes to store a collection of correlated

variables X:=(X_1,X_2,...,X_n), using as little space as possible, such that

each individual X_i can be recovered quickly with few (ideally constant)

memory accesses. 

In this talk, we focus on the natural case of compressing "Markov chains,"

i.e., storing a length-n walk on any (possibly directed) constant-size graph

G. Denoting by k(G,n) the number of length-n walks on G, we show that there is

a succinct data structure storing a walk using lg_2 k(G,n) + O(lg n) bits of

space, such that each vertex along the walk can be decoded in constant time on

a word-RAM. If the graph is strongly connected (e.g., undirected), the space

can be improved to only lg_2 k(G,n) + 5 bits.

Joint work with Emanuele Viola and Omri Weinstein.

Bio: Huacheng Yu is an associate research scholar in the department of

computer science at Princeton University. Prior to Princeton, he was a postdoc

in the Theory of Computation group at Harvard University, after receiving his

PhD from Stanford University in 2017.