DROPS

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.59

Testing Tensor Products of Algebraic Codes

Authors: Sumegha Garg, Madhu Sudan, and Gabriel Wu

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract

Motivated by recent advances in locally testable codes and quantum LDPCs based on robust testability of tensor product codes, we explore the local testability of tensor products of (an abstraction of) algebraic geometry codes. Such codes are parameterized by, in addition to standard parameters such as block length n and dimension k, their genus g. We show that the tensor product of two algebraic geometry codes is robustly locally testable provided n = Ω((k+g)²). Apart from Reed-Solomon codes, this seems to be the first explicit family of two-wise tensor codes of high dual distance that is robustly locally testable by the natural test that measures the expected distance of a random row/column from the underlying code.

Cite as

Sumegha Garg, Madhu Sudan, and Gabriel Wu. Testing Tensor Products of Algebraic Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 59:1-59:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{garg_et_al:LIPIcs.APPROX/RANDOM.2025.59,
  author =	{Garg, Sumegha and Sudan, Madhu and Wu, Gabriel},
  title =	{{Testing Tensor Products of Algebraic Codes}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{59:1--59:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.59},
  URN =		{urn:nbn:de:0030-drops-244254},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.59},
  annote =	{Keywords: Algebraic geometry codes, Robust testability, Tensor products of codes}
}

Search Results

Documents authored by Wu, Gabriel

Testing Tensor Products of Algebraic Codes

Abstract

Cite as

Thanks for your feedback!

Could not send message