Rutgers Discrete Mathematics Seminar

Title: Concentration of Random Linear Spaces

Speaker: Swastik Kopparty, Rutgers University

Date: Tuesday, September 20, 2011 2:00pm

Location: Hill Center, Room 425, Rutgers University, Busch Campus, Piscataway, NJ


Let S be a random d-dimensional linear subspace of F_2^n. How many points of S could lie in a small region? Specifically, for a radius p, we are interested in the largest t such that almost surely there is no Hamming ball of radius p that contains more than t points of S. We find the asymptotic behavior of t; it turns out that the answer is not much different from the case when S is chosen to be a uniformly random subset of F_2^n of size 2^d!

In the language of error-correcting codes, this determines the list-decodability of random linear codes, and shows that these codes are as list-decodable as general random codes.

Joint work with Venkatesan Guruswami and Johan Hastad.