Matching-vector families and LDCs over large modulo

Zeev Dvir, Guangda Hu

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

3 Citations (Scopus)

Abstract

We prove new upper bounds on the size of families of vectors in ℤm n with restricted modular inner products, when m is a large integer. More formally, if ui,...,ut ∈ ℤm n and v1,...,vt ∈ ℤm n 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

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

Fingerprint

Error-correcting Codes
Modulo
Query Complexity
Scalar, inner or dot product
Encoding
Upper bound
Integer
Family

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

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
Dvir, Zeev ; Hu, Guangda. / Matching-vector families and LDCs over large modulo. Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 16th International Workshop, APPROX 2013 and 17th International Workshop, RANDOM 2013, Proceedings. 2013. pp. 513-526 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{1b1dd03db73f405686e9b00e1c7e462f,
title = "Matching-vector families and LDCs over large modulo",
abstract = "We prove new upper bounds on the size of families of vectors in ℤm n with restricted modular inner products, when m is a large integer. More formally, if ui,...,ut ∈ ℤm n and v1,...,vt ∈ ℤm n 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].",
author = "Zeev Dvir and Guangda Hu",
year = "2013",
month = "10",
day = "15",
doi = "https://doi.org/10.1007/978-3-642-40328-6_36",
language = "English (US)",
isbn = "9783642403279",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "513--526",
booktitle = "Approximation, Randomization, and Combinatorial Optimization",

}

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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8096 LNCS, pp. 513-526, 16th 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, 8/21/13. https://doi.org/10.1007/978-3-642-40328-6_36

Matching-vector families and LDCs over large modulo. / Dvir, Zeev; Hu, Guangda.

Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 16th International Workshop, APPROX 2013 and 17th International Workshop, RANDOM 2013, Proceedings. 2013. p. 513-526 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8096 LNCS).

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

TY - GEN

T1 - Matching-vector families and LDCs over large modulo

AU - Dvir, Zeev

AU - Hu, Guangda

PY - 2013/10/15

Y1 - 2013/10/15

N2 - We prove new upper bounds on the size of families of vectors in ℤm n with restricted modular inner products, when m is a large integer. More formally, if ui,...,ut ∈ ℤm n and v1,...,vt ∈ ℤm n 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].

AB - We prove new upper bounds on the size of families of vectors in ℤm n with restricted modular inner products, when m is a large integer. More formally, if ui,...,ut ∈ ℤm n and v1,...,vt ∈ ℤm n 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].

UR - http://www.scopus.com/inward/record.url?scp=84885209167&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84885209167&partnerID=8YFLogxK

U2 - https://doi.org/10.1007/978-3-642-40328-6_36

DO - https://doi.org/10.1007/978-3-642-40328-6_36

M3 - Conference contribution

SN - 9783642403279

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 513

EP - 526

BT - Approximation, Randomization, and Combinatorial Optimization

ER -

Dvir Z, Hu G. 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. 2013. p. 513-526. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-40328-6_36