PaperlayerView exact revision on arXiv

Source-linked AI summary

Locally Testable Codes with constant rate, distance, and locality

Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, Shahar Mozes

arXiv:2111.04808v2cs.ITcs.CCmath.GRmath.IT

TL;DR

The paper addresses whether locally testable codes can simultaneously have constant rate, distance, and locality. It constructs such codes using two-dimensional left-right Cayley complexes, achieving polynomial-time infinite families with any rate 0 < r < 1 and parameters depending polynomially or inversely polynomially on 1 − r. The construction also introduces a square-based analogue of expander codes, while relying on dependent local constraints and specific expanding complexes.

  • Problem

    Whether LTCs with constant rate, constant distance, and constant locality exist has been an outstanding open question, despite the potential to test received words before decoding.

  • Method

    The paper builds codes on left-right Cayley complexes, placing codeword bits on squares and enforcing fixed base-code constraints around edges, with local tensor-code tests lifted globally by expansion.

  • Results

    For every 0 < r < 1, the paper gives a polynomial-time infinite family of LTCs with rate r, constant distance δ, and constant-query locality q.

  • Takeaways & Limitations

    The construction establishes the existence of c^3-LTCs and provides a two-dimensional analogue of expander codes with functions on squares rather than edges.

  • Takeaways & Limitations

    The construction requires dependent local constraints and a suitable family of expanding left-right Cayley complexes; the paper also notes unsettled issues in related high-dimensional approaches.

Abstract

from arXiv · show

A locally testable code (LTC) is an error-correcting code that has a property-tester. The tester reads $q$ bits that are randomly chosen, and rejects words with probability proportional to their distance from the code. The parameter $q$ is called the locality of the tester. LTCs were initially studied as important components of PCPs, and since then the topic has evolved on its own. High rate LTCs could be useful in practice: before attempting to decode a received word, one can save time by first quickly testing if it is close to the code. An outstanding open question has been whether there exist "$c^3$-LTCs", namely LTCs with *c*onstant rate, *c*onstant distance, and *c*onstant locality. In this work we construct such codes based on a new two-dimensional complex which we call a left-right Cayley complex. This is essentially a graph which, in addition to vertices and edges, also has squares. Our codes can be viewed as a two-dimensional version of (the one-dimensional) expander codes, where the codewords are functions on the squares rather than on the edges.

1 Introduction

The paper constructs the first LTC family with constant rate, distance, and locality, using a new two-dimensional left-right Cayley complex with squares. The construction extends expander-code ideas by placing codeword bits on squares and enforcing local base-code constraints around edges.

  • Background: A locally testable code uses a randomized tester that reads q bits and rejects words with probability proportional to their distance from the code.The query count q is the tester's locality.
  • Contribution: The authors construct the first family of LTCs with constant rate, constant distance, and constant locality.For every 0 < r < 1, the construction gives an infinite family with rate r, distance δ, and q-query local testability, using a polynomial-time construction.
  • Construction: Codeword bits lie on squares, while neighboring squares around each edge must form codewords in fixed base codes.Around a vertex, these constraints form an intermediate tensor code, which is tested locally and then lifted to the global code through expansion.
  • Construction: The codes use a left-right Cayley complex, a graph augmented with squares generated by alternating left and right Cayley edges.Vertices are group elements, edges arise from left or right multiplication, and each compatible pair of generators defines a square.
  • Comparison: The construction differs from one-dimensional expander codes because its constraints have many dependencies, enabling local violations to propagate rather than remain isolated.This dependency structure is important for detecting words that are far from the code.
  • Outlook: The left-right Cayley complexes are presented as new two-dimensional objects that may merit study beyond their use in LTCs.The paper raises the question of whether higher-dimensional analogues exist.

2 Preliminaries

The preliminaries define expander graphs, linear and tensor codes, and the testing notions used later. They also explain agreement testability as a relationship between disagreement of local views and distance from the tensor code.

  • 2.1 Expander Graphs: A λ-one-sided expander is a d-regular graph whose non-leading eigenvalues are at most λd.The Alon–Chung lemma converts induced-subgraph average degree into lower bounds on vertex and edge mass.
  • 2.2 Error Correcting Codes: A linear error-correcting code is a subspace of F2^n, with rate given by relative dimension and distance by minimum relative nonzero Hamming weight.
  • 2.2 Error Correcting Codes: The tensor code C1 ⊗ C2 consists of matrices whose rows lie in C2 and columns lie in C1.Its dimension is the product of the component dimensions, and its distance is the product of their distances.
  • 2.2 Error Correcting Codes: Tensor-code testing samples a random row or column and checks membership in the corresponding component code.The quality of this test is measured by robust testability, relating rejection probability to distance from the tensor code.
  • 2.2 Error Correcting Codes: Agreement testability bounds the fraction of local rows or columns needing modification by the disagreement between row-wise and column-wise views.Agreement testability and robust testability are equivalent notions up to the stated parameter correspondence.

3 The Left-Right Cayley Complex

The left-right Cayley complex augments two Cayley graphs with squares generated by left and right multiplication. Under the total no-conjugacy condition, its local structure is regular and supports a parallel random walk whose expansion properties are used later.

  • 3 The Left-Right Cayley Complex: The construction adds two-dimensional square faces to a graph, with each square forming a four-cycle.
  • 3 The Left-Right Cayley Complex: For a group G with symmetric generators A and B, vertices are G, A-edges multiply on the left, and B-edges multiply on the right.The resulting left-right structure creates many four-cycles through local commutativity.
  • 3 The Left-Right Cayley Complex: Squares are equivalence classes [a,g,b] of triples, representing four vertices connected by alternating A- and B-edges.
  • 3 The Left-Right Cayley Complex: Under (TNC), each vertex has |A| + |B| distinct neighbors, each square has four distinct vertices, and A × B indexes the squares around each vertex.
  • 3 The Left-Right Cayley Complex: The parallel random walk moves an edge to the other edge with the same label in a uniformly chosen incident square.For A-edges and B-edges, the corresponding label-restricted walks are standard walks on Cay(G, B) and Cay(G, A), respectively.

4 Error Correcting Code on a Left-Right Cayley Complex

The paper places tensor-code constraints on the squares of a left-right Cayley complex, producing a global code whose rate, distance, and local testability follow from the base codes and expansion. Local tests inspect all squares around a vertex and detect distance through violated constraints.

  • 4 Error Correcting Code on a Left-Right Cayley Complex: The global code assigns fixed base codes CA and CB to A- and B-edges, while each vertex carries the tensor code CA ⊗ CB on its incident squares.Using the same base code on every edge preserves the local tensor structure needed for local testability.
  • 4 Error Correcting Code on a Left-Right Cayley Complex: For a bipartite underlying graph, the code rate is at least 2(ρAρB) − 1, matching the corresponding expander-code bound for local rate ρAρB.
  • 4 Error Correcting Code on a Left-Right Cayley Complex: If both Cayley graphs are λ-expanders, the global distance is bounded below by both δAδB(δA − λ) and δBδA(δB − λ).The proof propagates nonzero rows and columns of a local tensor code through the two expander graphs.
  • 4 Error Correcting Code on a Left-Right Cayley Complex: The local tester reads the |A| · |B| squares around a random vertex and checks whether they form the tensor code CA ⊗ CB.The distance to the global code is at most a constant multiple of the fraction of violated local tests.
  • 4 Error Correcting Code on a Left-Right Cayley Complex: An iterative correction algorithm either finds a nearby codeword when the rejection fraction is small or certifies substantial disagreement among local views.For sufficiently small constant distance, the same procedure also acts as a decoder.

5 A Concrete Construction

The construction combines suitable base codes with explicit left-right Cayley complexes to obtain an infinite family of locally testable error-correcting codes with constant rate, distance, and locality.

  • 5 A Concrete Construction: For every 0 < r < 1, the construction gives an explicit infinite family with rate at least r, distance at least δ, and κ-local testability using q queries.The family is obtained from left-right Cayley complexes and base codes.
  • 5 A Concrete Construction: Explicit left-right Cayley complexes arise from groups Gi = PSL2(qi) with generating sets Ai and Bi whose Cayley graphs are λ-expanders.The generating sets have size D, satisfy condition (TNC), and support the required complex construction.
  • 5 A Concrete Construction: The resulting global codes Ci combine the complex with the base code and have rate at least r and κ-locality with D^2 queries.Their distance is bounded below by a positive constant under the construction’s parameter choices.
  • 5.1.1 Random LDPC Codes: Random LDPC codes provide the base codes because expansion of their factor graphs yields constant rate and distance, while tensoring gives robust testability.The factor-graph expansion implies a unique-neighbor property and therefore distance; tensor-product results provide robust testability.

6 Good Left-Right Cayley Complexes

This section gives explicit infinite families of left-right Cayley complexes with controlled generator sizes and arbitrarily small spectral parameters. These complexes supply the expanding structures needed for the paper’s locally testable-code construction.

  • 6 Good Left-Right Cayley Complexes: These complexes complete the geometric part of the LTC construction because the code proof requires left-right Cayley complexes with sufficiently large spectral gap.The paper combines the explicit expanding complexes with suitable base codes to complete the locally testable-code construction.
  • 6 Good Left-Right Cayley Complexes: For every λ > 0, the construction provides infinitely many groups whose two Cayley graphs have normalized second eigenvalues at most λ.The parameter can be made λ = Θ(k^-1/2), making both Cayley graphs quasi-Ramanujan.
  • 6 Good Left-Right Cayley Complexes: The construction uses two generating sets with different element orders: elements of B_i have order 2, while elements of A_i have order greater than 2, ensuring (TNC).In the PSL2(q^i) construction, A_i and B_i each have size q + 1 and satisfy (TNC).
  • 6 Good Left-Right Cayley Complexes: Explicit families of finite groups with symmetric generators A_i and B_i satisfy (TNC) and have both Cayley graphs as Ramanujan expanders.For odd prime powers q, the generators can have equal size q + 1, with normalized second eigenvalues at most 2(q + 1)^-1/2.
  • 6 Good Left-Right Cayley Complexes: The resulting left-right Cayley complexes can be constructed explicitly from PSL2(q^i), with generator sizes divisible by a prescribed d_0 and expansion bounded by λ ⩽ 8D^-1/2.The stated lemma applies when q is an odd prime power meeting the specified lower bound and D is the common generator size.

A Robust Testability and Agreement Testability

This section establishes that agreement testability and robust testability of tensor-product codes are quantitatively equivalent. Each notion yields the other with parameters determined by the component-code distances.

  • A Robust Testability and Agreement Testability: Robust testability with parameter τ implies agreement testability with κ = 2τδ_1δ_2.Here δ_i denotes the distance of component code C_i.
  • A Robust Testability and Agreement Testability: When both component codes have distance δ, the first implication simplifies to κ = τδ^2.
  • A Robust Testability and Agreement Testability: Agreement testability with parameter κ implies robust testability with τ = κ.
Loading 2111.04808v2…