Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLimitations of Mean-Based Algorithms for Trace Reconstruction at Small Distance
73
0
0.0
(
0
)
Added by
Minshen Zhu
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Trace reconstruction considers the task of recovering an unknown string $x in {0,1}^n$ given a number of independent traces, i.e., subsequences of $x$ obtained by randomly and independently deleting every symbol of $x$ with some probability $p$. The information-theoretic limit of the number of traces needed to recover a string of length $n$ are still unknown. This limit is essentially the same as the number of traces needed to determine, given strings $x$ and $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 on the one hand that 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. 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.
rate research
Read More
Mean-based reconstruction is a fundamental, natural approach to worst-case trace reconstruction over channels with synchronization errors. It is known that $exp(O(n^{1/3}))$ traces are necessary and sufficient for mean-based worst-case trace reconstruction over the deletion channel, and this result was also extended to certain channels combining deletions and geometric insertions of uniformly random bits. In this work, we use a simple extension of the original complex-analytic approach to show that these results are examples of a much more general phenomenon: $exp(O(n^{1/3}))$ traces suffice for mean-based worst-case trace reconstruction over any memoryless channel that maps each input bit to an arbitrarily distributed sequence of replications and insertions of random bits, provided the length of this sequence follows a sub-exponential distribution.
Bailey showed that the general pointwise forecasting for stationary and ergodic time series has a negative solution. However, it is known that for Markov chains the problem can be solved. Morvai showed that there is a stopping time sequence ${lambda_n}$ such that $P(X_{lambda_n+1}=1|X_0,...,X_{lambda_n}) $ can be estimated from samples $(X_0,...,X_{lambda_n})$ such that the difference between the conditional probability and the estimate vanishes along these stoppping times for all stationary and ergodic binary time series. We will show it is not possible to estimate the above conditional probability along a stopping time sequence for all stationary and ergodic binary time series in a pointwise sense such that if the time series turns out to be a Markov chain, the predictor will predict eventually for all $n$.
Consider a collection of random variables attached to the vertices of a graph. The reconstruction problem requires to estimate one of them given `far away observations. Several theoretical results (and simple algorithms) are available when their joint probability distribution is Markov with respect to a tree. In this paper we consider the case of sequences of random graphs that converge locally to trees. In particular, we develop a sufficient condition for the tree and graph reconstruction problem to coincide. We apply such condition to colorings of random graphs. Further, we characterize the behavior of Ising models on such graphs, both with attractive and random interactions (respectively, `ferromagnetic and `spin glass).
Bures distance holds a special place among various distance measures due to its several distinguished features and finds applications in diverse problems in quantum information theory. It is related to fidelity and, among other things, it serves as a bona fide measure for quantifying the separability of quantum states. In this work, we calculate exact analytical results for the mean root fidelity and mean square Bures distance between a fixed density matrix and a random density matrix, and also between two random density matrices. In the course of derivation, we also obtain spectral density for product of above pairs of density matrices. We corroborate our analytical results using Monte Carlo simulations. Moreover, we compare these results with the mean square Bures distance between reduced density matrices generated using coupled kicked tops and find very good agreement.
We consider a broad class of Approximate Message Passing (AMP) algorithms defined as a Lipschitzian functional iteration in terms of an $ntimes n$ random symmetric matrix $A$. We establish universality in noise for this AMP in the $n$-limit and validate this behavior in a number of AMPs popularly adapted in compressed sensing, statistical inferences, and optimizations in spin glasses.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
