Abstract
I will describe recent advances in linear sketching over finite fields. 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) and Hosseini and Lovett.