Trace reconstruction of matrices and hypermatrices

Abstract 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 left parenthesis ModifyingAbove upper O With tilde left parenthesis n Superscript d divided by left parenthesis d plus 2 right parenthesis Baseline right parenthesis right parenthesis exp ⁡ ( O ~ ( n d / ( d + 2 ) ) ) $\exp (\widetilde {O}(n^{d/(d+2)}))$ traces suffice to reconstruct any unknown n times n n × n $n\times n$ matrix (for d equals 2 d = 2 $d=2$ ) and any unknown n Superscript times d n × d $n^{\times 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 1 $1$ , we improve this upper bound by showing that exp left parenthesis ModifyingAbove upper O With tilde left parenthesis n Superscript 3 divided by 7 Baseline right parenthesis right parenthesis exp ⁡ ( O ~ ( n 3 / 7 ) ) $\exp (\widetilde {O}(n^{3/7}))$