[Colloquium] THEORY TALK TODAY: Venkatesan Guruswami
Katie Casey
caseyk at cs.uchicago.edu
Fri May 28 08:15:52 CDT 2010
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF CHICAGO
Date: Friday, May 28, 2010
Time: 2:30 p.m.
Place: Ryerson 251, 1100 E. 58th Street
----------------------------------------------------------
Speaker: Venatesan Guruswami
From: Carnegie Mellon University
Web: http://www.cs.cmu.edu/~venkatg/
Title: List decodability of random linear codes
Abstract: CFor every fixed finite field F_q, 0 < p < 1-1/q, and epsilon > 0, we prove that with high probability a random subspace C of F_q^n of dimension (1-h_q(p)-epsilon)n has the property that every Hamming ball of radius pn has at most O(1/epsilon) elements of C. (Here h_q(x) is the q-ary entropy function.)
This answers a basic open question concerning the list-decodability of linear codes, showing that a list size of O(1/epsilon) suffices to have rate within epsilon of the "list decoding capacity" 1-h_q(p). This matches up to constant factors the list-size achieved by general (non-linear) random codes, and gives an exponential improvement over the best previously known list-size bound of q^{O(1/epsilon)}.
The main technical ingredient in our proof is a strong upper bound on the probability that m random vectors chosen from a Hamming ball centered at the origin have too many (more than O(m)) vectors from their linear span also belong to the ball.
The talk will be self-contained and not assume any coding theory background.
Joint work with Johan Hastad and Swastik Kopparty.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20100528/750c5f45/attachment.htm
More information about the Colloquium
mailing list