Improved Subexponential Upper Bounds for $3$-Restricted Matching Vector Families

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\le \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.

11 pages