CS Events Monthly View


How to Store a Random Walk


Download as iCal file

Wednesday, September 25, 2019, 11:00am



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.

Speaker: Huacheng Yu


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.

Location : CoRE A 301


Rutgers/DIMACS Theory of Computing Seminar

Event Type: Seminar



Princeton University