Search

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 = \Omega((k+g)^2)$. Apart from Reed-Solomon codes, this seems to be the first explicit family of codes of super-constant dual distance that is robustly locally testable., Comment: 12 pages

While it is known that using network coding can significantly improve the throughput of directed networks, it is a notorious open problem whether coding yields any advantage over the multicommodity flow (MCF) rate in undirected networks. It was conjectured by Li and Li (2004) that the answer is "no". In this paper we show that even a small advantage over MCF can be amplified to yield a near-maximum possible gap. We prove that any undirected network with $k$ source-sink pairs that exhibits a $(1+\varepsilon)$ gap between its MCF rate and its network coding rate can be used to construct a family of graphs $G'$ whose gap is $\log(|G'|)^c$ for some constant $c < 1$. The resulting gap is close to the best currently known upper bound, $\log(|G'|)$, which follows from the connection between MCF and sparsest cuts. Our construction relies on a gap-amplifying graph tensor product that, given two graphs $G_1,G_2$ with small gaps, creates another graph $G$ with a gap that is equal to the product of the previous two, at the cost of increasing the size of the graph. We iterate this process to obtain a gap of $\log(|G'|)^c$ from any initial gap., Comment: 20 pages