Researchers Claim Locally-Testable-Code Breakthrough With Exotic Multi-Dimensional Graph

"A team of researchers has finally created a long-sought locally testable code that can immediately betray whether it's been corrupted..." reports Quanta magazine. "Many thought local testability would never be achieved in its ideal form." Now, in a preprint released on November 8, the computer scientist Irit Dinur of the Weizmann Institute of Science and four mathematicians, Shai Evra, Ron Livne, Alex Lubotzky and Shahar Mozes, all at the Hebrew University of Jerusalem, have found it. "It's one of the most remarkable phenomena that I know of in mathematics or computer science," said Tom Gur of the University of Warwick. "It's been the holy grail of an entire field." Their new technique transforms a message into a super-canary, an object that testifies to its health better than any other message yet known. Any corruption of significance that is buried anywhere in its superstructure becomes apparent from simple tests at a few spots. "This is not something that seems plausible," said Madhu Sudan of Harvard University. "This result suddenly says you can do it." Most prior methods for encoding data relied on randomness in some form. But for local testability, randomness could not help. Instead, the researchers had to devise a highly nonrandom graph structure entirely new to mathematics, which they based their new method on. It is both a theoretical curiosity and a practical advance in making information as resilient as possible.... To get a sense of what their graph looks like, imagine observing it from the inside, standing on a single edge. They construct their graph such that every edge has a fixed number of squares attached. Therefore, from your vantage point you'd feel as if you were looking out from the spine of a booklet. However, from the other three sides of the booklet's pages, you'd see the spines of new booklets branching from them as well. Booklets would keep branching out from each edge ad infinitum. "It's impossible to visualize. That's the whole point," said Lubotzky. "That's why it is so sophisticated...." [A] test at one node can reveal information about errors from far away nodes. By making use of higher dimensions, the graph is ultimately connected in ways that go beyond what we typically even think of as connections... It establishes a new state of the art for error-correcting codes, and it also marks the first substantial payoff from bringing the mathematics of high-dimensional expanders to bear on codes... Practical and theoretical applications should soon follow. Different forms of locally testable codes are now being used in decentralized finance, and an optimal version will allow even better decentralized tools.

Read more of this story at Slashdot.