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.