CMI Seminar: Grigory Yaroslavtsev

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