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.
See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math