Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR25-136 | 26th September 2025 21:35

Robust Local Testability of Tensor Products of Constant-Rate Algebraic Geometry Codes

RSS-Feed




TR25-136
Authors: Sumegha Garg, Akash Sengupta
Publication: 27th September 2025 19:48
Downloads: 124
Keywords: 


Abstract:

We study the robust local testability of tensor products of two Algebraic-Geometry (AG) codes. In particular, we prove that \textit{constant rate} AG codes are robust locally testable. This significantly generalizes the seminal result of Polishchuk-Spielman [PS24], which proved robust local testability of Reed-Solomon codes. We establish an algebraic-geometric framework that enables us to geometrically interpret codewords in tensor products of AG codes. Thereby, we use tools from intersection theory of algebraic surfaces to prove a divisibility criterion for AG codes, that generalizes the bivariate divisibility result of Polishchuk-Spielman.

Over the years, robust local testability of tensor products has played a key role in the development of classical locally testable codes (LTCs) as well as quantum Low Density Parity Check (qLDPC) codes and quantum Locally Testable Codes (qLTCs). To the best of our knowledge, after Reed-Solomon codes, our result provides the first explicit family of robustly locally testable codes with constant rate and linear dual-distance. Moreover, our result, when combined with [GG24], yields new explicit families of good quantum CSS codes of length $N$ which are locally testable with locality $O(\sqrt{N})$ and constant soundness.



ISSN 1433-8092 | Imprint