Search Mailing List Archives


Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] [theory-lunch] Ray Li on Error correcting codes

Hongyang Zhang hongyang at cs.stanford.edu
Mon Mar 5 11:24:23 PST 2018


H
​i Everyone

This Thursday, Rai Li will tell us about ​
*Random linear binary codes have smaller list sizes than uniformly random
binary codes*
*​. *See abstract below.

As before​, we meet from *noon to 1pm*, at *Gates 463a*.

​-----------------------------------------------------​
Abstract:

List decodable error correcting codes (Elias 1957, Wozencraft 1958) are a
widely applicable generalization uniquely decodable codes. Unfortunately,
for binary codes, for many years the only known optimal
(capacity-achieving) list-decodable codes were uniformly random codes, and
even now all capacity-achieving binary list decodable codes are
non-explicit. A great deal of work has established that random linear codes
are as list-decodable as uniformly random codes, bringing us closer to
explicit, capacity-achieving list decodable codes. In this talk, we discuss
a recent result that, in fact, random linear binary codes are more
list-decodable than uniformly random binary codes, in the sense that the
achievable list size is, with high probability, strictly smaller for random
linear binary codes than for uniformly random binary codes. The result
combines an upper bound for random linear binary codes, based on a
potential function given in (Guruswami, Håstad, Sudan, Zuckerman, 2002),
and a lower bound for uniformly random binary codes that tightens a result
of (Guruswami, Narayanan, 2014). Time permitting, we also discuss
corollaries of our technique, which include an application to rank metric
codes.

Based on joint work with Mary Wootters.
​----------​--------------------------------------------


Best,
Hongyang
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20180305/891fc28d/attachment-0002.html>


More information about the theory-seminar mailing list