Minshen Zhu
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Minshen Zhu has a total of 12 co-authors. Here are the top co-authors by number of shared publications:
- Elena Grigorescu
University of Waterloo, Waterloo, Canada
4 shared publications - Shubhang Kulkarni
University of Illinois, Urbana-Champaign, Urbana, USA
3 shared publications - Gabriel Istrate
University of Bucharest
2 shared publications - Karthekeyan Chandrasekaran
University of Illinois
2 shared publications - Madhu Sudan
School of Engineering and Applied Sciences Harvard University Cambridge Massachusetts USA
2 shared publications - Alexander R. Block
Georgetown University
1 shared publication
Latest Publications
- 13 February 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (4) , 2591-2603
On k-Mer-Based and Maximum Likelihood Estimation Algorithms for Trace Reconstruction
The goal of the trace reconstruction problem is to recover a string$\mathbf {x}\in \{0,1\}^{n}$ given many independent traces of x, where a trace is a subsequence obtained from deleting bits of x independently with some given probability$p\in [0,1$ ). A recent result of Chase (STOC 2021) shows how x can be determined (in exponential time) from$\exp ({O}(n^{1/5})\log ^{5} n)$ traces. This is the state-of-the-art result on the sample complexity of trace reconstruction. In this paper we consider two kinds of algorithms for the trace reconstruction problem. We first observe that the bound of Chase, which is based on statistics of arbitrary length-k subsequences, can also be obtained by considering the “k-mer statistics”, i.e., statistics regarding occurrences of contiguous k-bit strings (a.k.a, k-mers) in the initial string x, for$k = 2n^{1/5}$ . Mazooji and Shomorony (arXiv.2210.10917) show that such statistics (called k-mer density map) can be estimated within$\varepsilon $ accuracy from$ {\mathrm {poly}} (n, 2^{k}, 1/ {\varepsilon })$ traces. We call an algorithm to be k-mer-based if it reconstructs x given estimates of the k-mer density map. Such algorithms essentially capture all the analyses in the worst-case and smoothed-complexity models of the trace reconstruction problem we know of so far. Our first, and technically more involved, result shows that any k-mer-based algorithm for trace reconstruction must use$\exp (\Omega (n^{1/5} \sqrt {\log n}))$ traces, thus establishing the optimality of this number of traces. The analysis of this result also shows that the analysis technique used by Chase (STOC 2021) is essentially tight, and hence new techniques are needed in order to improve the worst-case upper bound. This result is shown by considering an appropriate class of real polynomials, that have been previously studied in the context of trace estimation (De, O’Donnell, Servedio. Annals of Probability 2019; Nazarov, Peres. STOC 2017), and proving that two of these polynomials are very close to each other on an arc in the complex plane. Our proof of the proximity of such polynomials uses new technical ingredients that allow us to focus on just a few coefficients of these polynomials. Our second, simple, result considers the performance of the Maximum Likelihood Estimator (MLE), which specifically picks the source string that has the maximum likelihood to generate the samples (traces). We show that the MLE algorithm uses a nearly optimal number of traces, i.e., up to a factor of n in the number of samples needed for an optimal algorithm, and show that this factor of n loss may be necessary under general “model estimation” settings.- 13 February 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (4) , 2591-2603
On k-Mer-Based and Maximum Likelihood Estimation Algorithms for Trace Reconstruction
The goal of the trace reconstruction problem is to recover a string$\mathbf {x}\in \{0,1\}^{n}$ given many independent traces of x, where a trace is a subsequence obtained from deleting bits of x independently with some given probability$p\in [0,1$ ). A recent result of Chase (STOC 2021) shows how x can be determined (in exponential time) from$\exp ({O}(n^{1/5})\log ^{5} n)$ traces. This is the state-of-the-art result on the sample complexity of trace reconstruction. In this paper we consider two kinds of algorithms for the trace reconstruction problem. We first observe that the bound of Chase, which is based on statistics of arbitrary length-k subsequences, can also be obtained by considering the “k-mer statistics”, i.e., statistics regarding occurrences of contiguous k-bit strings (a.k.a, k-mers) in the initial string x, for$k = 2n^{1/5}$ . Mazooji and Shomorony (arXiv.2210.10917) show that such statistics (called k-mer density map) can be estimated within$\varepsilon $ accuracy from$ {\mathrm {poly}} (n, 2^{k}, 1/ {\varepsilon })$ traces. We call an algorithm to be k-mer-based if it reconstructs x given estimates of the k-mer density map. Such algorithms essentially capture all the analyses in the worst-case and smoothed-complexity models of the trace reconstruction problem we know of so far. Our first, and technically more involved, result shows that any k-mer-based algorithm for trace reconstruction must use$\exp (\Omega (n^{1/5} \sqrt {\log n}))$ traces, thus establishing the optimality of this number of traces. The analysis of this result also shows that the analysis technique used by Chase (STOC 2021) is essentially tight, and hence new techniques are needed in order to improve the worst-case upper bound. This result is shown by considering an appropriate class of real polynomials, that have been previously studied in the context of trace estimation (De, O’Donnell, Servedio. Annals of Probability 2019; Nazarov, Peres. STOC 2017), and proving that two of these polynomials are very close to each other on an arc in the complex plane. Our proof of the proximity of such polynomials uses new technical ingredients that allow us to focus on just a few coefficients of these polynomials. Our second, simple, result considers the performance of the Maximum Likelihood Estimator (MLE), which specifically picks the source string that has the maximum likelihood to generate the samples (traces). We show that the MLE algorithm uses a nearly optimal number of traces, i.e., up to a factor of n in the number of samples needed for an optimal algorithm, and show that this factor of n loss may be necessary under general “model estimation” settings.- 18 April 2022
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 68 (10) , 6790-6801
Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Edit Distance
Trace reconstruction considers the task of recovering an unknown string $\mathbf {x}\in \{0,1\}^{n}$ given a number of independent “traces”, i.e., subsequences of $\mathbf {x}$ obtained by randomly and independently deleting every symbol of $\mathbf {x}$ with some probability $p$ . The information-theoretic limit of the number of traces needed to recover a string of length $n$ is still unknown. This limit is essentially the same as the number of traces needed to determine, given strings $\mathbf {x}$ and $\mathbf {y}$ and traces of one of them, which string is the source. The most-studied class of algorithms for the worst-case version of the problem are “mean-based” algorithms. These are a restricted class of distinguishers that only use the mean value of each coordinate on the given samples. In this work we study limitations of mean-based algorithms on strings at small Hamming or edit distance. We show that, on the one hand, distinguishing strings that are nearby in Hamming distance is “easy” for such distinguishers. On the other hand, we show that distinguishing strings that are nearby in edit distance is “hard” for mean-based algorithms. Along the way, we also describe a connection to the famous Prouhet-Tarry-Escott (PTE) problem, which shows a barrier to finding explicit hard-to-distinguish strings: namely such strings would imply explicit short solutions to the PTE problem, a well-known difficult problem in number theory. Furthermore, we show that the converse is also true, thus, finding explicit solutions to the PTE problem is equivalent to the problem of finding explicit strings that are hard-to-distinguish by mean-based algorithms. Our techniques rely on complex analysis arguments that involve careful trigonometric estimates, and algebraic techniques that include applications of Descartes’ rule of signs for polynomials over the reals.
- 18 April 2022
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 68 (10) , 6790-6801
Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Edit Distance
Trace reconstruction considers the task of recovering an unknown string $\mathbf {x}\in \{0,1\}^{n}$ given a number of independent “traces”, i.e., subsequences of $\mathbf {x}$ obtained by randomly and independently deleting every symbol of $\mathbf {x}$ with some probability $p$ . The information-theoretic limit of the number of traces needed to recover a string of length $n$ is still unknown. This limit is essentially the same as the number of traces needed to determine, given strings $\mathbf {x}$ and $\mathbf {y}$ and traces of one of them, which string is the source. The most-studied class of algorithms for the worst-case version of the problem are “mean-based” algorithms. These are a restricted class of distinguishers that only use the mean value of each coordinate on the given samples. In this work we study limitations of mean-based algorithms on strings at small Hamming or edit distance. We show that, on the one hand, distinguishing strings that are nearby in Hamming distance is “easy” for such distinguishers. On the other hand, we show that distinguishing strings that are nearby in edit distance is “hard” for mean-based algorithms. Along the way, we also describe a connection to the famous Prouhet-Tarry-Escott (PTE) problem, which shows a barrier to finding explicit hard-to-distinguish strings: namely such strings would imply explicit short solutions to the PTE problem, a well-known difficult problem in number theory. Furthermore, we show that the converse is also true, thus, finding explicit solutions to the PTE problem is equivalent to the problem of finding explicit strings that are hard-to-distinguish by mean-based algorithms. Our techniques rely on complex analysis arguments that involve careful trigonometric estimates, and algebraic techniques that include applications of Descartes’ rule of signs for polynomials over the reals.
- 31 May 2021
- Published by Springer Nature in Algorithmica
- Vol. 83 (8) , 2427-2468
The Maximum Binary Tree Problem
- 31 May 2021
- Published by Springer Nature in Algorithmica
- Vol. 83 (8) , 2427-2468
The Maximum Binary Tree Problem
- Open Access
Locally Decodable/Correctable Codes for Insertions and Deletions
Recent efforts in coding theory have focused on building codes for insertions and deletions, called insdel codes, with optimal trade-offs between their redundancy and their error-correction capabilities, as well as efficient encoding and decoding algorithms. In many applications, polynomial running time may still be prohibitively expensive, which has motivated the study of codes with super-efficient decoding algorithms. These have led to the well-studied notions of Locally Decodable Codes (LDCs) and Locally Correctable Codes (LCCs). Inspired by these notions, Ostrovsky and Paskin-Cherniavsky (Information Theoretic Security, 2015) generalized Hamming LDCs to insertions and deletions. To the best of our knowledge, these are the only known results that study the analogues of Hamming LDCs in channels performing insertions and deletions. Here we continue the study of insdel codes that admit local algorithms. Specifically, we reprove the results of Ostrovsky and Paskin-Cherniavsky for insdel LDCs using a different set of techniques. We also observe that the techniques extend to constructions of LCCs. Specifically, we obtain insdel LDCs and LCCs from their Hamming LDCs and LCCs analogues, respectively. The rate and error-correction capability blow up only by a constant factor, while the query complexity blows up by a poly log factor in the block length. Since insdel locally decodable/correctble codes are scarcely studied in the literature, we believe our results and techniques may lead to further research. In particular, we conjecture that constant-query insdel LDCs/LCCs do not exist.
Open AccessLocally Decodable/Correctable Codes for Insertions and Deletions
Recent efforts in coding theory have focused on building codes for insertions and deletions, called insdel codes, with optimal trade-offs between their redundancy and their error-correction capabilities, as well as efficient encoding and decoding algorithms. In many applications, polynomial running time may still be prohibitively expensive, which has motivated the study of codes with super-efficient decoding algorithms. These have led to the well-studied notions of Locally Decodable Codes (LDCs) and Locally Correctable Codes (LCCs). Inspired by these notions, Ostrovsky and Paskin-Cherniavsky (Information Theoretic Security, 2015) generalized Hamming LDCs to insertions and deletions. To the best of our knowledge, these are the only known results that study the analogues of Hamming LDCs in channels performing insertions and deletions. Here we continue the study of insdel codes that admit local algorithms. Specifically, we reprove the results of Ostrovsky and Paskin-Cherniavsky for insdel LDCs using a different set of techniques. We also observe that the techniques extend to constructions of LCCs. Specifically, we obtain insdel LDCs and LCCs from their Hamming LDCs and LCCs analogues, respectively. The rate and error-correction capability blow up only by a constant factor, while the query complexity blows up by a poly log factor in the block length. Since insdel locally decodable/correctble codes are scarcely studied in the literature, we believe our results and techniques may lead to further research. In particular, we conjecture that constant-query insdel LDCs/LCCs do not exist.
- Open Access
The Maximum Binary Tree Problem
We introduce and investigate the approximability of the maximum binary tree problem (MBT) in directed and undirected graphs. The goal in MBT is to find a maximum-sized binary tree in a given graph. MBT is a natural variant of the well-studied longest path problem, since both can be viewed as finding a maximum-sized tree of bounded degree in a given graph. The connection to longest path motivates the study of MBT in directed acyclic graphs (DAGs), since the longest path problem is solvable efficiently in DAGs. In contrast, we show that MBT in DAGs is in fact hard: it has no efficient $\exp(-O(\log n/ \log \log n))$-approximation algorithm under the exponential time hypothesis, where $n$ is the number of vertices in the input graph. In undirected graphs, we show that MBT has no efficient $\exp(-O(\log^{0.63}{n}))$-approximation under the exponential time hypothesis. Our inapproximability results rely on self-improving reductions and structural properties of binary trees. We also show constant-factor inapproximability assuming $\text{P}\neq \text{NP}$. In addition to inapproximability results, we present algorithmic results along two different flavors: (1) We design a randomized algorithm to verify if a given directed graph on $n$ vertices contains a binary tree of size $k$ in $2^k \text{poly}(n)$ time. (2) Motivated by the longest heapable subsequence problem, introduced by Byers, Heeringa, Mitzenmacher, and Zervas (ANALCO 2011), which is equivalent to MBT in permutation DAGs, we design efficient algorithms for MBT in bipartite permutation graphs.Open AccessThe Maximum Binary Tree Problem
We introduce and investigate the approximability of the maximum binary tree problem (MBT) in directed and undirected graphs. The goal in MBT is to find a maximum-sized binary tree in a given graph. MBT is a natural variant of the well-studied longest path problem, since both can be viewed as finding a maximum-sized tree of bounded degree in a given graph. The connection to longest path motivates the study of MBT in directed acyclic graphs (DAGs), since the longest path problem is solvable efficiently in DAGs. In contrast, we show that MBT in DAGs is in fact hard: it has no efficient $\exp(-O(\log n/ \log \log n))$-approximation algorithm under the exponential time hypothesis, where $n$ is the number of vertices in the input graph. In undirected graphs, we show that MBT has no efficient $\exp(-O(\log^{0.63}{n}))$-approximation under the exponential time hypothesis. Our inapproximability results rely on self-improving reductions and structural properties of binary trees. We also show constant-factor inapproximability assuming $\text{P}\neq \text{NP}$. In addition to inapproximability results, we present algorithmic results along two different flavors: (1) We design a randomized algorithm to verify if a given directed graph on $n$ vertices contains a binary tree of size $k$ in $2^k \text{poly}(n)$ time. (2) Motivated by the longest heapable subsequence problem, introduced by Byers, Heeringa, Mitzenmacher, and Zervas (ANALCO 2011), which is equivalent to MBT in permutation DAGs, we design efficient algorithms for MBT in bipartite permutation graphs.