Title: Discrepancy problems for linear spaces or decoding problems above capacity
Abstract:
Consider the following class of problems: let S be a family of subsets of F_q^n and let C be a linear subspace of F_q^n of some specified dimension k. The S-deviation of C is the maximum over B in S of how much |C intersect B| deviates from its expectation over a random C. The goal is to determine the smallest S-deviation achievable.
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 particular 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 in n. Despite being a natural question with important applications in secret sharing, very little was known until the present work.
In this talk, I will discuss ongoing research on this problem and present the progress we have made so far.
Joint work with: Dean Doron, Tal Leonov, Nicolas Resch, and João Ribeiro.