2026/03/17 by Daniella Bar-Lev
#cs.IT #math.CO #math.IT
We study the problem of coded information retrieval for block-structured data, motivated by DNA-based storage systems where a database is partitioned into multiple files that must each be recoverable as an atomic unit. We initiate and formalize the block-structured retrieval problem, wherein k information symbols are partitioned into two files F1 and F2 of sizes s1 and s2 = k - s1. The objective is to characterize the set of achievable expected retrieval time pairs (E1(G), E2(G)) over all [n,k] linear codes with generator matrix G. We derive a family of linear lower bounds via mutual exclusivity of recovery sets and develop a nonlinear geometric bound via column projection that holds for every linear code. For codes with no mixed columns, this yields the hyperbolic constraint s1/E1 + s2/E2 ≤ 1, which we conjecture to hold universally whenever max\s1,s2\ ≥ 2. We analyze explicit codes, such as the identity code, file-dedicated MDS codes, and the systematic global MDS code, and compute their exact expected retrieval times. For file-dedicated codes, we prove MDS optimality within the family and verify the hyperbolic constraint. For global MDS codes, we establish dominance by the proportional local MDS allocation via a convex-ordering argument for hypergeometric distributions, simplifying and extending prior work to the asymmetric case. Finally, we characterize the limiting achievability region as n → ∞: the hyperbolic boundary is asymptotically achieved by file-dedicated MDS codes, and is conjectured to be the exact boundary of the limiting achievability region.