Source author record

Alex Zhai

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.PR math.CO Data Structures and Algorithms Information Theory math.IT math.OC math.ST quant-ph Statistics Theory Systems and Control

Catalog footprint

Research overview

9works

10topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Subpolynomial trace reconstruction for random strings and arbitrary deletion probability

The insertion-deletion channel takes as input a bit string ${\bf x}\in\{0,1\}^{n}$ , and outputs a string where bits have been deleted and inserted independently at random. The trace reconstruction problem is to recover $\bf x$ from many independent outputs (called "traces") of the insertion-deletion channel applied to $\bf x$ . We show that if $\bf x$ is chosen uniformly at random, then $\exp(O(\log^{1/3} n))$ traces suffice to reconstruct $\bf x$ with high probability. For the deletion channel with deletion probability $q < 1/2$ the earlier upper bound was $\exp(O(\log^{1/2} n))$ . The case of $q\geq 1/2$ or the case where insertions are allowed has not been previously analyzed, and therefore the earlier upper bound was as for worst-case strings, i.e., $\exp(O( n^{1/3}))$ . We also show that our reconstruction algorithm runs in $n^{1+o(1)}$ time. A key ingredient in our proof is a delicate two-step alignment procedure where we estimate the location in each trace corresponding to a given bit of $\bf x$ . The alignment is done by viewing the strings as random walks and comparing the increments in the walk associated with the input string and the trace, respectively.

preprint2020arXiv

The CLT in high dimensions: quantitative bounds via martingale embedding

We introduce a new method for obtaining quantitative convergence rates for the central limit theorem (CLT) in a high dimensional setting. Using our method, we obtain several new bounds for convergence in transportation distance and entropy, and in particular: (a) We improve the best known bound, obtained by the third named author, for convergence in quadratic Wasserstein transportation distance for bounded random vectors; (b) We derive the first non-asymptotic convergence rate for the entropic CLT in arbitrary dimension, for general log-concave random vectors; (c) We give an improved bound for convergence in transportation distance under a log-concavity assumption and improvements for both metrics under the assumption of strong log-concavity. Our method is based on martingale embeddings and specifically on the Skorokhod embedding constructed by the first named author.

preprint2016arXiv

When multiplicative noise stymies control

We consider the stabilization of an unstable discrete-time linear system that is observed over a channel corrupted by continuous multiplicative noise. Our main result shows that if the system growth is large enough, then the system cannot be stabilized in a second-moment sense. This is done by showing that the probability that the state magnitude remains bounded must go to zero with time. Our proof technique recursively bounds the conditional density of the system state (instead of focusing on the second moment) to bound the progress the controller can make. This sidesteps the difficulty encountered in using the standard data-rate theorem style approach; that approach does not work because the mutual information per round between the system state and the observation is potentially unbounded. It was known that a system with multiplicative observation noise can be stabilized using a simple memoryless linear strategy if the system growth is suitably bounded. In this paper, we show that while memory cannot improve the performance of a linear scheme, a simple non-linear scheme that uses one-step memory can do better than the best linear scheme.

preprint2014arXiv

Exponential concentration of cover times

We prove an exponential concentration bound for cover times of general graphs in terms of the Gaussian free field, extending the work of Ding-Lee-Peres and Ding. The estimate is asymptotically sharp as the ratio of hitting time to cover time goes to zero. The bounds are obtained by showing a stochastic domination in the generalized second Ray-Knight theorem, which was shown to imply exponential concentration of cover times by Ding. This stochastic domination result appeared earlier in a preprint of Lupu, but the connection to cover times was not mentioned.

preprint2014arXiv

Surprise probabilities in Markov chains

In a Markov chain started at a state $x$ , the hitting time $τ(y)$ is the first time that the chain reaches another state $y$ . We study the probability $\mathbf{P}_x(τ(y) = t)$ that the first visit to $y$ occurs precisely at a given time $t$ . Informally speaking, the event that a new state is visited at a large time $t$ may be considered a "surprise". We prove the following three bounds: 1) In any Markov chain with $n$ states, $\mathbf{P}_x(τ(y) = t) \le \frac{n}{t}$ . 2) In a reversible chain with $n$ states, $\mathbf{P}_x(τ(y) = t) \le \frac{\sqrt{2n}}{t}$ for $t \ge 4n + 4$ . 3) For random walk on a simple graph with $n \ge 2$ vertices, $\mathbf{P}_x(τ(y) = t) \le \frac{4e \log n}{t}$ . We construct examples showing that these bounds are close to optimal. The main feature of our bounds is that they require very little knowledge of the structure of the Markov chain. To prove the bound for random walk on graphs, we establish the following estimate conjectured by Aldous, Ding and Oveis-Gharan (private communication): For random walk on an $n$ -vertex graph, for every initial vertex $x$ , $\sum_y \left( \sup_{t \ge 0} p^t(x, y) \right) = O(\log n).$

preprint2013arXiv

On multiple peaks and moderate deviations for supremum of Gaussian field

We prove two theorems concerning extreme values of general Gaussian fields. Our first theorem concerns with the concept of multiple peaks. A theorem of Chatterjee states that when a centered Gaussian field admits the so-called superconcentration property, it typically attains values near its maximum on multiple near-orthogonal sites, known as multiple peaks. We improve his theorem in two aspects: (i) the number of peaks attained by our bound is of the order $\exp(c / σ^2)$ (as opposed to Chatterjee's polynomial bound in $1/σ$ ), where $σ$ is the standard deviation of the supremum of the Gaussian field, which is assumed to have variance at most $1$ and (ii) our bound need not assume that the correlations are non-negative. We also prove a similar result based on the superconcentration of the free energy. As primary applications, we infer that for the S-K spin glass model on the $n$ -hypercube and directed polymers on $\mathbb{Z}_n^2$ , there are polynomially (in $n$ ) many near-orthogonal sites that achieve values near their respective maxima. Our second theorem gives an upper bound on moderate deviation for the supremum of a general Gaussian field. While the Gaussian isoperimetric inequality implies a sub-Gaussian concentration bound for the supremum, we show that the exponent in that bound can be improved under the assumption that the expectation of the supremum is of the same order as that of the independent case.

preprint2011arXiv

An asymptotic result concerning a question of Wilf

Let $Λ$ be a numerical semigroup with embedding dimension $e(Λ)$ . Define $c(Λ)$ to be one plus the largest integer not in $Λ$ , and define $c'(Λ)$ to be the number of elements in $Λ$ less than $c(Λ)$ . It was asked by Wilf whether $\frac{c'(Λ)}{c(Λ)} \ge \frac{1}{e(Λ)}$ always holds. We prove an asymptotic version of this conjecture: we show that for a fixed positive integer $k$ and any $ε> 0$ , the inequality $\frac{c'(Λ)}{c(Λ)} \ge \frac{1}{k} - ε$ holds for all but finitely many numerical semigroups $Λ$ satisfying $e(Λ) = k$ .

preprint2011arXiv

Fibonacci-like growth of numerical semigroups of a given genus

We give an asymptotic estimate of the number of numerical semigroups of a given genus. In particular, if $n_g$ is the number of numerical semigroups of genus $g$ , we prove that $n_g$ tends to $S ϕ^g$ , where $ϕ$ is the golden ratio, and $S$ is a constant, resolving several related conjectures concerning the growth of $n_g$ . In addition, we show that the proportion of numerical semigroups of genus $g$ satisfying $f < 3m$ approaches 1 as $g \rightarrow \infty$ , where $m$ is the multiplicity and $f$ is the Frobenius number.

preprint2011arXiv

Robust Quantum State Transfer in Random Unpolarized Spin Chains

We propose and analyze a new approach for quantum state transfer between remote spin qubits. Specifically, we demonstrate that coherent quantum coupling between remote qubits can be achieved via certain classes of random, unpolarized (infinite temperature) spin chains. Our method is robust to coupling strength disorder and does not require manipulation or control over individual spins. In principle, it can be used to attain perfect state transfer over arbitrarily long range via purely Hamiltonian evolution and may be particularly applicable in a solid-state quantum information processor. As an example, we demonstrate that it can be used to attain strong coherent coupling between Nitrogen-Vacancy centers separated by micrometer distances at room temperature. Realistic imperfections and decoherence effects are analyzed.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Alex Zhai

Research overview

Is this your work?

9 publications

Subpolynomial trace reconstruction for random strings and arbitrary deletion probability

The CLT in high dimensions: quantitative bounds via martingale embedding

When multiplicative noise stymies control

Exponential concentration of cover times

Surprise probabilities in Markov chains

On multiple peaks and moderate deviations for supremum of Gaussian field

An asymptotic result concerning a question of Wilf

Fibonacci-like growth of numerical semigroups of a given genus

Robust Quantum State Transfer in Random Unpolarized Spin Chains

See the researcher in context

Building this map preview