Reconstruction of hypermatrices from subhypermatrices

Abstract

For a given $n$, what is the smallest number $k$ such that every sequence of length $n$ is determined by the multiset of all its $k$-subsequences? This is called the $k$-deck problem for sequence reconstruction, and has been generalized to the two-dimensional case -- reconstruction of $n\times n$-matrices from submatrices. Previous works show that the smallest $k$ is at most $O(n^{\frac{1}{2}})$ for sequences and at most $O(n^{\frac{2}{3}})$ for matrices. We study this $k$-deck problem for general dimension $d$ and prove that, the smallest $k$ is at most $O(n^{\frac{d}{d+1}})$ for reconstructing a $d$ dimensional hypermatrix of order $n$ from the multiset of all its subhypermatrices of order $k$.

arXiv comment25 pages, 4 figures