[Colloquium] Talk by Venkatesan Guruswami, CMU on May, 28, 2010

[Katie Casey]

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/20100512/a3cc00db/attachment.htm