Explicit constructions reduce overlap in mathematical data sets

Explicit Subspace Evasive Sets via Subspace Designs

Discrete MathematicsInformation Theory

Summary

This paper deals with special sets of points in mathematical spaces where few points lie in any small sub-area. The authors provide a new, clear method to create these sets, improving previous methods that had bigger overlaps. This helps build more efficient coding systems that can recover data with fewer errors and smaller output lists. Their approach combines existing coding designs with new local sets to achieve better results. This development overcomes past limitations in constructing such coding techniques.

What this means in practice

Authors

Joshua Brakensiek, Yeyuan Chen, Mahdi Cheraghchi, Rohan Goyal, Venkatesan Guruswami, Aaron Putterman, Zihan Zhang

Abstract

Given a finite field $\mathbb F_q$, we say that a set $A\subseteq \mathbb F^n_q$ is an $(r,c)$ subspace evasive set if and only if for any affine subspace $U\subseteq \mathbb F^n_q$ with bounded dimension $\dim(U)\leq r$, the intersection size $|A\cap U|$ is at most $c$. The probabilistic method shows the existence of $(r,c)$ subspace evasive sets with $|A| = q^{(1-ε) n}$ with $c = O(r/ε)$. However, the best explicit constructions by Dvir--Lovett (STOC 2012) and Ben-Aroya--Shinkar (CJTCS 2013) have $c$ growing as an exponential function of $r$. Here, we give an explicit construction of such subspace evasive set that achieves the intersection bound $c=O(\min(r\log(r/ε)/ε, r^2/ε))$ when both $r$ and $1/ε$ are constants. Our approach is simple and the key idea is to compose subspace design codes (Guruswami-Xing, STOC 2013) with a suitably chosen ``local'' subspace evasive set. As a corollary, we give the first construction of an explicit (strongly) capacity-achieving list-recoverable code with nearly optimal list size, circumventing all previously-known barriers to construction.