Papers for

distributed storage teams

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Network coding outperforms traditional methods in undirected multiple unicast

The Multiple Unicast Conjecture is False

Abstract: The undirected multiple-unicast conjecture [LL04] asserts that network coding offers no throughput advantage over multicommodity flow. We refute this conjecture by constructing a deterministic linear network code over $\mathbb{F}_9$ on a 182-vertex bipartite subgraph of the point-line incidence graph of $\mathrm{PG}(2,9)$. The construction supports $157$ independent unicast sessions at common coding rate at least $1$, while every fractional multicommodity flow has common rate at most $147/157$. By the amplification theorem of~[BGS17], this yields a family of undirected multiple-unicast instances with coding gap $Ω((\log n)^\varepsilon)$ for some $\varepsilon>0$. We also introduce a nondeterministic model of network coding based on locally verifiable certificates, which guides our construction and may be of independent interest. Building on the high-girth graph and error-correcting code framework of [BH25], we use GPT-6 to find a nondeterministic counterexample based on a new choice of Reed--Solomon local codes, and then convert this example into a causal code using an edge orientation and local search.

Wed 7 OctInformation TheoryComputational ComplexityDiscrete Mathematics
The gist
The paper challenges a long-standing belief that network coding can't improve data flow in certain network settings. The authors built a special kind of communication setup that proves network coding can send more information simultaneously than standard routing methods. They used advanced math and computer tools to design and verify this example. This means network coding has more potential for improving how data travels in networks than previously thought.
Open → 2610.10108v1

Reed-Solomon codes decoded efficiently up to their error limit

Reed-Solomon Codes at Capacity: Algorithmic List-Decoding and Proximity Gaps

Abstract: Understanding the limits of list-decodability of Reed-Solomon codes has been one of the most important open problems in algebraic coding theory. Recently, Brakensiek, Chen, Putterman, Zhang, and Zheng, in a remarkable breakthrough, showed that Reed-Solomon (RS) codes over fields of large characteristic are algorithmically list-decodable all the way up to capacity. Building on this result, Jeronimo subsequently extended these techniques to solve the proximity-gaps question for RS codes. In this article, we give a unified and transparent exposition of these results.

Tue 6 OctComputational ComplexityInformation Theory
The gist
Reed-Solomon codes help protect digital data from errors, but understanding how far they can be correctly decoded when many errors occur has been a major challenge. The authors explain recent breakthroughs that show these codes can be efficiently decoded even when errors reach the theoretical maximum limit. They also clarify related results about distinguishing valid codewords from near misses. This work brings together those findings into a clear and unified explanation.
Open → 2610.08610v1