Recoverable systems on lines and grids
Alexander Barg, Ohad Elishco, Ryan Gabrys, Eitan Yaakobi · 2022 IEEE International Symposium on Information Theory (ISIT) · 2022
A storage code is an assignment of symbols to the vertices of a connected graph G(V, E) with the property that the value of each vertex is a function of the values of its neighbors, or more generally, of a certain neighborhood of the vertex in G. Under the name of recoverable systems, a class of storage codes on ${\mathbb{Z}}$ was recently studied relying on methods from constrained systems and ergodic theory. In this work, we address the question of the maximum capacity of recoverable systems on ${\mathbb{Z}}$ and ${{\mathbb{Z}}^2}$ from a combinatorial perspective. We establish a closed form formula for the capacity of several one- and two-dimensional systems, depending on their recovery set, using connections between storage codes, graphs, anticodes, and difference-avoiding sets.