Combinatorics Seminar 2018

Speaker: Yi Li (李翼), Nanyang Technological University

Date: Tue, Jul 10, 2018

Time: 15:30 - 16:30

Venue: Middle Meeting Room

Title: Estimating the Schatten norms of matrices in streaming model


A popular data stream model in theoretical computer science is the turnstile streaming model, in which there is an underlying vector which is initialized to 0 and receives incremental updates to its coordinates. The goal is to compute some function of the vector at the end of the stream without essentially storing the entire vector. A well-studied problem in the literature is approximating the ell_p norms of the vector; in this talk I shall study the analogous problem of estimating matrix Schatten norms. I intend to present a systematic summary of latest results on the space complexity of estimating the Schatten p-norms of an n x n matrix in the turnstile streaming model. Both kinds of space complexities, bit complexity and sketching dimension, are considered.