Papers for

telecommunications system builders

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Explicit constructions reduce overlap in mathematical data sets

Explicit Subspace Evasive Sets via Subspace Designs

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.

Wed 11 NovDiscrete MathematicsInformation Theory
The gist
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.
Open → 2611.14909v1