Source author record

Oanh Nguyen

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 Computational Complexity

Catalog footprint

Research overview

9works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

Convergence of higher derivatives of random polynomials with independent roots

Let $μ$ be a probability measure on $\mathbb C$ , and let $P_n$ be the random polynomial whose zeros are sampled independently from $μ$ . We study the asymptotic distribution of zeros of high-order derivatives of $P_n$ . We show that, for large classes of measures $μ$ , the empirical distribution of zeros of the $k$ -th derivative converges back to $μ$ for all derivative orders $k=o(n/\log n)$ . This includes all discrete measures and a broad family of measures satisfying a mild dimension-nondegeneracy condition. We further establish a robustness result showing that, for arbitrary $μ$ , even after adding a vanishing proportion of roots drawn from a dimension-nondegenerate perturbation, the derivative zero measures still converge back to $μ$ . These results break the previously known logarithmic barrier on the order of differentiation and demonstrate that the limiting root distribution is preserved under differentiation of order growing nearly linearly with the degree.

preprint2024arXiv

Concentration inequalities for the number of real zeros of Kac polynomials

We study concentration inequalities for the number of real roots of the classical Kac polynomials $f_{n} (x) = \sum_{i=0}^n ξ_i x^i$ where $ξ_i$ are independent random variables with mean 0, variance 1, and uniformly bounded $(2+\ep_0)$-moments. We establish polynomial tail bounds, which are optimal, for the bulk of roots. For the whole real line, we establish sub-optimal tail bounds.

preprint2022arXiv

Real roots of random orthogonal polynomials with exponential weights

We consider random orthonormal polynomials $P_{n}(x)=\sum_{i=0}^{n}ξ_{i}p_{i}(x),$ where $ξ_{0}$ , . . . , $ξ_{n}$ are independent random variables with zero mean, unit variance and uniformly bounded $(2+\ep_0)$-moments, and $\{p_n\}_{n=0}^{\infty}$ is the system of orthonormal polynomials with respect to a general exponential weight $W$ on the real line. This class of orthogonal polynomials includes the popular Hermite and Freud polynomials. We establish universality for the leading asymptotics of the expected number of real roots of $P_n$ , both globally and locally. In addition, we find an almost sure limit of the measures counting all roots of $P_n.$ This is accomplished by introducing new ideas on applications of the inverse Littlewood-Offord theory in the context of the classical three term recurrence relation for orthogonal polynomials to establish anti-concentration properties, and by adapting the universality methods to the weighted random orthogonal polynomials of the form $W P_n.$

preprint2022arXiv

The number of limit cycles bifurcating from a randomly perturbed center

We consider the average number of limit cycles that bifurcate from a randomly perturbed linear center where the perturbation consists of random (bivariate) polynomials with independent coefficients. This problem reduces, by way of classical perturbation theory of the Poincaré first return map, to a problem on the real zeros of a random \emph{univariate} polynomial $\displaystyle f_n(x) = \sum_{m=0}^n c_m ξ_m x^m$ with independent coefficients $ξ_m$ having mean zero, variance 1 and $c_m \sim m^{-1/2}$ . This polynomial belongs to the class of {\it generalized Kac polynomials} at the critical regime. We provide asymptotics for the average number of real zeros and answer the question on bifurcating limit cycles. Additionally, we provide the correct order of the mean number of real roots in the subcritical regime.

preprint2020arXiv

Random trigonometric polynomials: universality and non-universality of the variance for the number of real roots

In this paper, we study the number of real roots of random trigonometric polynomials with iid coefficients. When the coefficients have zero mean, unit variance and some finite high moments, we show that the variance of the number of real roots is asymptotically linear in terms of the expectation; furthermore, the multiplicative constant in this linear relationship depends only on the kurtosis of the common distribution of the polynomial's coefficients. This result is in sharp contrast to the classical Kac polynomials whose corresponding variance depends only on the first two moments. Our result is perhaps the first paper to establish the variance for general distribution of the coefficients including discrete ones, for a model of random polynomials outside the family of the Kac polynomials. Our method gives a fine comparison framework throughout Edgeworth expansion, asymptotic Kac-Rice formula and a detailed analysis of characteristic functions.

preprint2020arXiv

Survival and extinction of epidemics on random graphs with general degrees

In this paper, we establish the necessary and sufficient criterion for the contact process on Galton-Watson trees (resp. random graphs) to exhibit the phase of extinction (resp. short survival). We prove that the survival threshold $λ_1$ for a Galton-Watson tree is strictly positive if and only if its offspring distribution $ξ$ has an exponential tail, i.e., $\mathbb{E} e^{cξ}<\infty$ for some $c>0$ , settling a conjecture by Huang and Durrett [12]. On the random graph with degree distribution $μ$ , we show that if $μ$ has an exponential tail, then for small enough $λ$ the contact process with the all-infected initial condition survives for $n^{1+o(1)}$ -time w.h.p. (short survival), while for large enough $λ$ it runs over $e^{Θ(n)}$ -time w.h.p. (long survival). When $μ$ is subexponential, we prove that the contact process w.h.p. displays long survival for any fixed $λ>0$ .

preprint2016arXiv

Packing Loose Hamilton Cycles

A subset $C$ of edges in a $k$ -uniform hypergraph $H$ is a \emph{loose Hamilton cycle} if $C$ covers all the vertices of $H$ and there exists a cyclic ordering of these vertices such that the edges in $C$ are segments of that order and such that every two consecutive edges share exactly one vertex. The binomial random $k$ -uniform hypergraph $H^k_{n,p}$ has vertex set $[n]$ and an edge set $E$ obtained by adding each $k$ -tuple $e\in \binom{[n]}{k}$ to $E$ with probability $p$ , independently at random. Here we consider the problem of finding edge-disjoint loose Hamilton cycles covering all but $o(|E|)$ edges, referred to as the \emph{packing problem}. While it is known that the threshold probability for the appearance of a loose Hamilton cycle in $H^k_{n,p}$ is $p=Θ\left(\frac{\log n}{n^{k-1}}\right)$ , the best known bounds for the packing problem are around $p=\text{polylog}(n)/n$ . Here we make substantial progress and prove the following asymptotically (up to a polylog $(n)$ factor) best possible result: For $p\geq \log^{C}n/n^{k-1}$ , a random $k$ -uniform hypergraph $H^k_{n,p}$ with high probability contains $N:=(1-o(1))\frac{\binom{n}{k}p}{n/(k-1)}$ edge-disjoint loose Hamilton cycles. Our proof utilizes and modifies the idea of "online sprinkling" recently introduced by Vu and the first author.

preprint2015arXiv

Anti-concentration for polynomials of independent random variables

We prove anti-concentration results for polynomials of independent random variables with arbitrary degree. Our results extend the classical Littlewood-Offord result for linear polynomials, and improve several earlier estimates. We discuss applications in two different areas. In complexity theory, we prove near optimal lower bounds for computing the Parity, addressing a challenge in complexity theory posed by Razborov and Viola, and also address a problem concerning OR functions. In random graph theory, we derive a general anti-concentration result on the number of copies of a fixed graph in a random graph.

preprint2014arXiv

On the number of real roots of random polynomials

Roots of random polynomials have been studied exclusively in both analysis and probability for a long time. A famous result by Ibragimov and Maslova, generalizing earlier fundamental works of Kac and Erdos-Offord, showed that the expectation of the number of real roots is $\frac{2}π \log n + o(\log n)$ . In this paper, we determine the true nature of the error term by showing that the expectation equals $\frac{2}π\log n + O(1)$ . Prior to this paper, such estimate has been known only in the gaussian case, thanks to works of Edelman and Kostlan.

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.