CMI Seminar: Grigory Yaroslavtsev

Tuesday October 15, 2019 4:00 PM

Advances in Linear Sketching over Finite Fields

Speaker: Grigory Yaroslavtsev, Indiana University, Bloomington
Location: Annenberg 314

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)"

Series Center for the Mathematics of Information (CMI) Seminar Series

Contact: Linda Taddeo at 626-395-6704 ltaddeo@caltech.edu
For more information visit: http://www.cmi.caltech.edu/events.shtml