Caltech Logo

CMI Seminar: Grigory Yaroslavtsev

Tuesday, October 15, 2019
4:00pm to 5:00pm
Add to Cal
Annenberg 314
Advances in Linear Sketching over Finite Fields
Grigory Yaroslavtsev, Assistant professor of Computer Science, Indiana University, Bloomington,

I will describe recent advances in linear sketching over finite fields and its relationship to log-rank conjecture and (quantum) communication complexity. For a function f: Z_p^n -> R a linear sketch modulo p is a distribution A over k x n matrices with entries in Z_p which for every x \in Z_p^n allows one to compute f(x) given access only to Ax. An important example here are binary sketches (corresponding to p = 2). I will describe recent structural results about the smallest dimension of k which enables linear sketching using the tools of Fourier analysis and communication complexity. In particular, if f is an XOR-function linear sketching over Z_2 turns out to be the optimal tool for the design of two-player one-way communication protocols (under the uniform distribution of x) as well as multi-player one-way broadcasting protocols with Omega(n) players (for any distribution of x).

Based on joint works with Kannan, Mossel and Sanyal (CCC'18), Hosseini and Lovett (CCC'19) and Zhou (RANDOM'19)"

For more information, please contact Linda Taddeo by phone at 626-395-6704 or by email at [email protected] or visit Mathematics of Information Seminar - Upcoming Events.