# CMI Seminar: Grigory Yaroslavtsev

**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