Abstract:
Consider the following class of problems: let S be a family of subsets of a high-dimensional vector space over a finite field, and let C be a linear subspace of some specified dimension. The discrepancy of C with respect to S is the maximum, over all sets B in S, of how much the size of the intersection of C and B deviates from its expected value for a random C. The goal is to determine how small this discrepancy can be.
In coding theory, this framework is particularly relevant when S is the family of all Hamming balls of a given radius, or the family of all combinatorial rectangles of a given side length. These correspond to the problems of list-decoding and list-recovery of linear codes, respectively.
While these problems are often studied in the below-capacity regime, they are much less understood above capacity, where the expected intersection size grows exponentially with the dimension. This regime is also relevant to applications in secret sharing.
In this talk, I will describe new results on the discrepancy of random linear spaces above capacity. Roughly speaking, they show that despite their rigid algebraic structure, random linear codes often distribute themselves across large structured sets almost as evenly as completely random sets. I will discuss the consequences for list-decoding and list-recovery, an application to secret sharing, and some of the ideas behind the proofs.
Joint work with Dean Doron, Tal Leonov, Henrique Navas, Nicolas Resch, and João Ribeiro.
