Trace reconstruction of matrices and hypermatrices

A trace of a sequence is generated by deleting each bit of the sequence independently with a fixed probability. The well-studied trace reconstruction problem asks how many traces are required to reconstruct an unknown binary sequence with high probability. In this paper, we study the multivariate version of this problem for matrices and hypermatrices, where a trace is generated by deleting each row/column of the matrix or each slice of the hypermatrix independently with a constant probability. Previously, Krishnamurthy et al. showed that exp(O(nd/(d+2))) traces suffice to reconstruct any unknown n× n matrix (for $d=2$) and any unknown n× d hypermatrix. By developing a dimension reduction procedure and establishing a multivariate version of the Littlewood-type result, we improve this upper bound by showing that exp(O(n3/7)) traces suffice to reconstruct any unknown n× n matrix, and exp(O(n3/5)) traces suffice to reconstruct any unknown n× d hypermatrix. This breaks the tendency to trivial exp(O(n)) as the dimension d grows.