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 multidimensional 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, Mazumdar, McGregor and Pal 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 that lower bounds sparse complex polynomials around $1$ , 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. In contrast to the earlier bound, our new exponent is bounded away from $1$ even as d becomes very large.