Query-Efficient Locally Decodable Codes of Subexponential Length

Yeow Meng Chee, Tao Feng, San Ling, Huaxiong Wang, Liang Feng ZhangComput. Complex 2013 · DOI

TL;DR

This paper introduces new constructions for query-efficient locally decodable codes (LDCs) with subexponential length. By leveraging a specific class of composite numbers related to Mersenne numbers, the authors significantly improve the query complexity of existing LDC constructions, leading to more efficient private information retrieval (PIR) schemes.

What Problem Does This Paper Address?

Locally Decodable Codes (LDCs) are a crucial tool in theoretical computer science, enabling the recovery of individual message symbols from a corrupted codeword by making only a few queries to the codeword. The efficiency of an LDC is measured by its query complexity (how many queries are needed) and its length (the size of the codeword relative to the message length). While significant progress has been made in constructing LDCs with low query complexity, achieving both low query complexity and subexponential length has been a major challenge.

Previous work by Yekhanin (2008) and Efremenko (2009) established constructions for 3-query LDCs of subexponential length, but these constructions relied on specific algebraic properties of certain composite numbers (like 511) and had limitations on the achievable query complexity for longer codewords. Itoh and Suzuki (2010) developed a composition method to improve these constructions, but the performance still hinged on finding "good" composite numbers that enable low-query LDCs. This paper addresses the problem of finding more such "good" composite numbers and using them to further enhance the query efficiency of LDCs and, consequently, PIR schemes.

Methods

The core of this paper lies in developing the algebraic theory behind Efremenko's framework for constructing LDCs. The authors:

  • Characterize "good" composite numbers: They identify a specific class of composite numbers, namely Mersenne numbers that are products of two distinct primes ($m = 2^t - 1 = pq$, where $t, p, q$ are primes), as being "good" for constructing 3-query LDCs. This characterization is based on algebraic properties related to S-matching families and S-decoding polynomials within Efremenko's framework.
  • Leverage Algebraic Theory: They delve into the properties of group rings, characters, and cyclotomic cosets to rigorously prove their characterization. This involves analyzing conditions derived from polynomial equations and matrix properties.
  • Computer Search: They perform a computer search to identify 50 such Mersenne numbers, expanding the known set of "good" composite numbers beyond 511.
  • Composition Method: They apply Itoh and Suzuki's composition method, using the newly found "good" composite numbers as building blocks. This method allows combining existing LDCs to create new ones with potentially lower query complexity for longer codeword lengths.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and uses computer search to identify specific numbers with desired properties, rather than relying on datasets for training or evaluation.

Key Insights and Ideas

  • Mersenne Numbers as "Good" Composites: The most significant insight is the discovery that Mersenne numbers of the form $2^t - 1 = pq$ (where $t, p, q$ are primes) possess the necessary algebraic properties to yield efficient 3-query LDCs within Efremenko's framework. This provides a systematic way to find new candidates for "good" composite numbers.
  • Algebraic Niceness Explained: The paper provides a deeper understanding of the "algebraic niceness" phenomenon in composite numbers that enables query complexity savings in LDCs.
  • Expanding the Toolkit: By identifying 50 new such numbers, the authors significantly expand the set of building blocks available for constructing LDCs, directly impacting the achievable query complexities.
  • Connection to Mersenne Primes: The work draws an interesting parallel to the open problem of determining the infinitude of Mersenne primes, suggesting that the set of "good" Mersenne numbers might also be infinite.

Key Results

The paper presents several key results that improve upon existing LDC and PIR schemes:

  • Improved Query Complexity for LDCs:
    • For every positive integer $r < 103$, they construct a $k$-query linear LDC of length $N_r$ where $k \le (\sqrt{3})^r$ if $r$ is even, and $k \le 8 \cdot (\sqrt{3})^{r-3}$ if $r$ is odd.
  • For every integer $r > 104$, they construct a $k$-query linear LDC of length $N_r$ where $k < (3/4)^{51} \cdot 2^r$.
  • These results represent significant improvements in query complexity compared to previous constructions, especially for larger $r$.
  • New PIR Schemes: By applying the newly constructed LDCs to known transformations, they obtain new information-theoretic PIR schemes with fewer servers and improved communication complexity.
  • Identification of New "Good" Numbers: They identify 50 Mersenne numbers of the form $2^t - 1 = pq$ that are "good" for constructing 3-query LDCs, answering open problems in the field.

Limitations and Future Work

  • Determining the Cardinality of $M_{2, \text{Mersenne}}$: A major open problem is to determine whether the set of "good" Mersenne numbers ($M_{2, \text{Mersenne}}$) is infinite. The authors conjecture it is, similar to the conjecture about Mersenne primes.
  • Disproving Membership in $M_2$: While the paper provides a method for finding numbers in $M_2$, it doesn't offer an easier way to disprove membership in $M_2$ than exhaustive search, except for specific cases like Corollary 3.26 showing $15 \notin M_2$.
  • Further Improvements: The authors suggest that identifying more "good" composite numbers in $M_2$ could lead to further improvements in LDC and PIR schemes. This implies that exploring other classes of composite numbers or refining the algebraic characterization could be fruitful.

Summary updated

BibTeX
@article{chee2013query,
  author = {Yeow Meng Chee and Tao Feng and San Ling and Huaxiong Wang and Liang Feng Zhang},
  title = {{Query-Efficient Locally Decodable Codes of Subexponential Length}},
  journal = {Comput. Complex.},
  year = {2013},
  doi = {10.1007/s00037-011-0017-1},
}
Figure