Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Academician O.B. Lupanov International Scientific Seminar "Discrete Mathematics and Its Applications"

On robust testability of product of random codes

Gleb Vyacheslavovich Kalachev, Pavel Panteleev

Published Jan 1, 2022• 0 citations
Publisher

Abstract

We study the robust testability of the tensor product line codes. It is shown that the product of two random linear codes are almost always robustly testable. This result has applications in the field of quantum codes and can be used for constructing efficiently decodable quantum LDPC codes.
DOI
10.20948/dms-2022-84

Related papers

Two-sided Robustly Testable Codes

Gleb Vyacheslavovich Kalachev, Pavel Panteleev

We show that the tensor product of two random linear codes is robustly testable with high probability. This implies that one can obtain pairs of linear codes such that their product and the product of their dual codes are simultaneously robustly testable. Such two-sided robustly testable codes (with a much weaker form of robustness) were the key ingredient in the recent constructions of asymptotically good quantum LDPC codes, which ensured their linear minimum distance. We hope that the existence of such codes with a stronger form of robustness, shown here, can be used to simplify the proofs and provide better distance bounds in these constructions. We also give new very simple examples of non-robustly testable codes. We show that if the parity-checks of two codes are mutually orthogonal, then their product is not robustly testable. In particular, this implies that the product of a code with its dual can never be robustly testable. We also study a property of a collection of linear codes called product-expansion, which can be viewed as a coboundary expansion of the cochain complex naturally associated with the product of these codes. We show that this property is related with the robust testability and the agreement testability of the products of codes.

arXiv:2206.09973•Jun 20, 2022•4 citations

Maximally Extendable Product Codes are Good Coboundary Expanders

Gleb Vyacheslavovich Kalachev, Pavel Panteleev

We investigate the coboundary expansion property of tensor product codes, known as product expansion, which plays an important role in recent constructions of good quantum LDPC codes and classical locally testable codes. Prior research has shown that this property is equivalent to agreement testability and robust testability for products of two codes with linear distance. However, for products of more than two codes, product expansion is a strictly stronger property. In this paper, we prove that a collection of an arbitrary number of random codes over a sufficiently large field has good product expansion. We believe that, in the case of four codes, the same ideas can be used to construct good quantum locally testable codes, in a way similar to the current constructions that use only products of two codes.

arXiv:2501.01411•Annual Symposium on Foundations of Computer Science•Dec 14, 2025•0 citations

Testing Tensor Products of Algebraic Codes

Sumegha Garg, Madhu Sudan, Wu, Gabriel

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)^2)$. 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.

arXiv:2410.22606•Leibniz international proceedings in informatics•Oct 30, 2024•0 citations

Testing Tensor Products of Algebraic Codes

Garg, Sumegha, Madhu Sudan, Wu, Gabriel

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.

•Jan 1, 2025•0 citations

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

Sumegha Garg, Akash Kumar Sengupta

We study the robust local testability of tensor products of two Algebraic-Geometry (AG) codes. In particular, we prove that constant rate AG codes are robust locally testable. This significantly generalizes the seminal result of Polishchuk-Spielman (1994), 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 Golowich-Guruswami (2024), yields new explicit families of good quantum CSS codes of length N which are locally testable with locality $O(\sqrt N )$ and constant soundness.

Annual Symposium on Foundations of Computer Science•Dec 14, 2025•0 citations

High-dimensional Expansion of Product Codes is Stronger than Robust and Agreement Testability

Gleb Vyacheslavovich Kalachev

We study the coboundary expansion property of product codes called product expansion, which played a key role in all recent constructions of good qLDPC codes. It was shown before that this property is equivalent to robust testability and agreement testability for products of two codes with linear distance. First, we show that robust testability for product of many codes with linear distance is equivalent to agreement testability. Second, we provide an example of product of three codes with linear distance which is robustly testable but not product expanding.

arXiv:2308.02889•Aug 5, 2023•0 citations
We show that the tensor product of two random linear codes is robustly testable with high probability. This implies that one can obtain pairs of linear codes such that their product and the product of their dual codes are simultaneously robustly testable. Such two-sided robustly testable codes (with a much weaker form of robustness) were the key ingredient in the recent constructions of asymptotically good quantum LDPC codes, which ensured their linear minimum distance. We hope that the existence of such codes with a stronger form of robustness, shown here, can be used to simplify the proofs and provide better distance bounds in these constructions. We also give new very simple examples of non-robustly testable codes. We show that if the parity-checks of two codes are mutually orthogonal, then their product is not robustly testable. In particular, this implies that the product of a code with its dual can never be robustly testable. We also study a property of a collection of linear codes called product-expansion, which can be viewed as a coboundary expansion of the cochain complex naturally associated with the product of these codes. We show that this property is related with the robust testability and the agreement testability of the products of codes.
We investigate the coboundary expansion property of tensor product codes, known as product expansion, which plays an important role in recent constructions of good quantum LDPC codes and classical locally testable codes. Prior research has shown that this property is equivalent to agreement testability and robust testability for products of two codes with linear distance. However, for products of more than two codes, product expansion is a strictly stronger property. In this paper, we prove that a collection of an arbitrary number of random codes over a sufficiently large field has good product expansion. We believe that, in the case of four codes, the same ideas can be used to construct good quantum locally testable codes, in a way similar to the current constructions that use only products of two codes.
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 nnn and dimension kkk, their genus ggg. We show that the tensor product of two algebraic geometry codes is robustly locally testable provided n=Ω((k+g)2)n = Ω((k+g)^2)n=Ω((k+g)2). 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.
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.
We study the robust local testability of tensor products of two Algebraic-Geometry (AG) codes. In particular, we prove that constant rate AG codes are robust locally testable. This significantly generalizes the seminal result of Polishchuk-Spielman (1994), 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 Golowich-Guruswami (2024), yields new explicit families of good quantum CSS codes of length N which are locally testable with locality O(N)O(\sqrt N )O(N​) and constant soundness.
We study the coboundary expansion property of product codes called product expansion, which played a key role in all recent constructions of good qLDPC codes. It was shown before that this property is equivalent to robust testability and agreement testability for products of two codes with linear distance. First, we show that robust testability for product of many codes with linear distance is equivalent to agreement testability. Second, we provide an example of product of three codes with linear distance which is robustly testable but not product expanding.