Improved Subexponential Upper Bounds for $3$-Restricted Matching Vector Families
Computational ComplexityDiscrete MathematicsInformation Theory
Summary
The authors study special pairs of vector lists called Matching Vector Families (MVFs), important in coding theory for creating efficient error-correcting codes. They focus on a specific type called 3-restricted MVFs in certain modular arithmetic settings. The authors improved the known upper limit on the size of these MVFs, showing they can’t be too large, using a new polynomial technique to better understand how sums of vectors behave. This advances previous results by providing tighter bounds when the modulus is not too big relative to the vector dimension.
Authors
Sidhant Saraogi
Abstract
Matching Vector families (MVFs) are defined by two ordered lists of vectors in $\mathbb{Z}_m^n$ whose inner products satisfy specific residue patterns modulo an integer $m$. Most famously, restricted MVFs are used to construct the best-known constant-query Locally Decodable codes (LDCs). We prove an upper bound of $2^{O\left(\sqrt{n\log n \log m}\right)}$ on the size of $3$-restricted MVFs in $\mathbb{Z}_m^n$ for $m \leq \sqrt{n}$, substantially improving on the previous best bound of $2^{O(n/\log n)}$ by Bhowmick, Dvir and Lovett (STOC'13, SICOMP'14). Our proof relies on a new polynomial method argument that controls collisions in sumsets of matching vectors.