### Abstract

A Matching Vector (MV) family modulo m is a pair of ordered lists U = (u_{1},..., u_{t}) and V = (v_{1},...,v_{t}) where u_{i}, v_{j} ∈ ℤ^{n} _{m} with the following inner product pattern: for any i, (u_{i}, v_{i})i = 0, and for any i ≠ j, (u_{i}, v_{i})≠ 0. A MV family is called q-restricted if inner products hui; vji take at most q different values. Our interest in MV families stems from their recent application in the construction of sub-exponential locally decodable codes (LDCs). There, q-restricted MV families are used to construct LDCs with q queries, and there is special interest in the regime where q is constant. When m is a prime it is known that such constructions yield codes with exponential block length. However, for composite m the behaviour is dramatically different. A recent work by Efremenko [8] (based on an approach initiated by Yekhanin [24]) gives the rst sub-exponential LDC with constant queries. It is based on a construction of a MV family of super-polynomial size by Grolmusz [10] modulo composite m. In this work, we prove two lower bounds on the block length of LDCs which are based on black box construction using MV families. When q is constant (or sufficiently small), we prove that such LDCs must have a quadratic block length. When the modulus m is constant (as it is in the construction of Efremenko [8]) we prove a super-polynomial lower bound on the block-length of the LDCs, assuming a well-known conjecture in additive combinatorics, the polynomial Freiman-Ruzsa conjecture over ℤ_{m}.

Original language | English (US) |
---|---|

Title of host publication | STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing |

Pages | 823-832 |

Number of pages | 10 |

DOIs | |

State | Published - 2013 |

Event | 45th Annual ACM Symposium on Theory of Computing, STOC 2013 - Palo Alto, CA, United States Duration: Jun 1 2013 → Jun 4 2013 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Other

Other | 45th Annual ACM Symposium on Theory of Computing, STOC 2013 |
---|---|

Country | United States |

City | Palo Alto, CA |

Period | 6/1/13 → 6/4/13 |

### All Science Journal Classification (ASJC) codes

- Software

### Keywords

- Locally decodable codes
- Matching vector families
- Restricted modular intersections

## Fingerprint Dive into the research topics of 'New bounds for matching vector families'. Together they form a unique fingerprint.

## Cite this

*STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing*(pp. 823-832). (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/2488608.2488713