Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 53 min ago
PreprintCC BY 4.0arXiv

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

  • Sidhant Saraogi
Open at sourcePDFDOICite

Abstract

Matching Vector families (MVFs) are defined by two ordered lists of vectors in ℤmn 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 2O(√(nlog n log m)) on the size of $3$-restricted MVFs in ℤmn for m ≤ √n, substantially improving on the previous best bound of 2O(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.

Related

  1. Diffusion Flow Matching: Dimension-Improved KL Bounds and Wasserstein Guarantees
    Marta Gentiloni Silveri, Giovanni Conforti, Alain Durmus
    arXivPreprintarXiv licenceFull textStatisticsarXiv
  2. List coloring C3-free planar graphs with a sparse matching of restricted lists
    Stephen G. Hartke, Yupei Li, Joseph Pappe +3
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Infinite Families of Counterexamples to a Conjecture of Liu and Qian and a Refined Inverse Theorem for Restricted Sumsets in ℤp
    Jiantao Li, Xinyi Liang
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv
  4. Approximation Families and the Statistical Efficiency of Denoising Score Matching
    Brian Miyatake
    arXivPreprintarXiv licenceFull textStatisticsarXiv
  5. Probabilistic Geodesic Flow Matching on Location-Scale Families
    Zeyuan Yu, Zhi Chang, Shiwei Lan
    arXivPreprintCC BY 4.0Full textProbabilityStatisticsarXiv

Cite

BibTeXRIS
BibTeX
@misc{saraogi2026improved,
  title = {{Improved Subexponential Upper Bounds for $3$-Restricted Matching Vector Families}},
  author = {Sidhant Saraogi},
  howpublished = {arXiv},
  year = {2026},
  month = aug,
  doi = {10.48550/arxiv.2608.27859},
  eprint = {2608.27859},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.27859},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Improved Subexponential Upper Bounds for $3$-Restricted Matching Vector Families
AU  - Sidhant Saraogi
PY  - 2026
DA  - 2026/08/28
PB  - arXiv
DO  - 10.48550/arxiv.2608.27859
UR  - https://arxiv.org/abs/2608.27859
AB  - Matching Vector families (MVFs) are defined by two ordered lists of vectors in ℤ_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(√(nlog n log m)) on the size of $3$-restricted MVFs in ℤ_m^n for m ≤ √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.
ER  -