Seminars & Colloquia Calendar

Download as iCal file

DIMACS Theory of Computing Seminar

How to store a random walk

Huacheng Yu (Princeton)

Location:  CoRE 301
Date & time: Wednesday, 25 September 2019 at 11:00AM - 12:00PM

 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.


Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.