Matching-vector families and LDCs over large modulo

Zeev Dvir, Guangda Hu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

We prove new upper bounds on the size of families of vectors in ℤmn with restricted modular inner products, when m is a large integer. More formally, if ui,...,ut ∈ ℤmn and v1,...,vt ∈ ℤmn satisfy 〈ui, vi〉 ≡ 0 (mod m) and 〈ui, vj〉 ≢ 0 (mod m) for all i ≠ j ∈ [t], we prove that t ≤ O(mn/2+8.47). This improves a recent bound of t ≤ mn/2+O(log(m)) by [BDL13] and is the best possible up to the constant 8.47 when m is sufficiently larger than n. The maximal size of such families, called 'Matching-Vector families', shows up in recent constructions of locally decodable error correcting codes (LDCs) and determines the rate of the code. Using our result we are able to show that these codes, called Matching-Vector codes, must have encoding length at least K19/18 for K-bit messages, regardless of their query complexity. This improves a known super linear bound of K2Ω(√log K) proved in [BDL13].

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization
Subtitle of host publicationAlgorithms and Techniques - 16th International Workshop, APPROX 2013 and 17th International Workshop, RANDOM 2013, Proceedings
Pages513-526
Number of pages14
DOIs
StatePublished - Oct 15 2013
Event16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2013 and the 17th International Workshop on Randomization and Computation, RANDOM 2013 - Berkeley, CA, United States
Duration: Aug 21 2013Aug 23 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8096 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2013 and the 17th International Workshop on Randomization and Computation, RANDOM 2013
CountryUnited States
CityBerkeley, CA
Period8/21/138/23/13

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Matching-vector families and LDCs over large modulo'. Together they form a unique fingerprint.

  • Cite this

    Dvir, Z., & Hu, G. (2013). Matching-vector families and LDCs over large modulo. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 16th International Workshop, APPROX 2013 and 17th International Workshop, RANDOM 2013, Proceedings (pp. 513-526). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8096 LNCS). https://doi.org/10.1007/978-3-642-40328-6_36