BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Nike Sun

Nike Sun appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.PRmath-phmath.MPcond-mat.stat-mechmath.CVDiscrete MathematicsComputational ComplexityData Structures and AlgorithmsMachine Learningmath.COmath.STStatistics Theory

Catalog footprint

What is connected

14works
12topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

14 published item(s)

preprint2022arXiv

On the Second Kahn--Kalai Conjecture

For any given graph $H$, we are interested in $p_\mathrm{crit}(H)$, the minimal $p$ such that the Erdős-Rényi graph $G(n,p)$ contains a copy of $H$ with probability at least $1/2$. Kahn and Kalai (2007) conjectured that $p_\mathrm{crit}(H)$ is given up to a logarithmic factor by a simpler "subgraph expectation threshold" $p_\mathrm{E}(H)$, which is the minimal $p$ such that for every subgraph $H'\subseteq H$, the Erdős-Rényi graph $G(n,p)$ contains \emph{in expectation} at least $1/2$ copies of $H'$. It is trivial that $p_\mathrm{E}(H) \le p_\mathrm{crit}(H)$, and the so-called "second Kahn-Kalai conjecture" states that $p_\mathrm{crit}(H) \lesssim p_\mathrm{E}(H) \log e(H)$ where $e(H)$ is the number of edges in $H$. In this article, we present a natural modification $p_\mathrm{E, new}(H)$ of the Kahn--Kalai subgraph expectation threshold, which we show is sandwiched between $p_\mathrm{E}(H)$ and $p_\mathrm{crit}(H)$. The new definition $p_\mathrm{E, new}(H)$ is based on the simple observation that if $G(n,p)$ contains a copy of $H$ and $H$ contains \emph{many} copies of $H'$, then $G(n,p)$ must also contain \emph{many} copies of $H'$. We then show that $p_\mathrm{crit}(H) \lesssim p_\mathrm{E, new}(H) \log e(H)$, thus proving a modification of the second Kahn--Kalai conjecture. The bound follows by a direct application of the set-theoretic "spread" property, which led to recent breakthroughs in the sunflower conjecture by Alweiss, Lovett, Wu and Zhang and the first fractional Kahn--Kalai conjecture by Frankston, Kahn, Narayanan and Park.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Sharp threshold sequence and universality for Ising perceptron models

We study a family of Ising perceptron models with $\{0,1\}$-valued activation functions. This includes the classical half-space models, as well as some of the symmetric models considered in recent works. For each of these models we show that the free energy is self-averaging, there is a sharp threshold sequence, and the free energy is universal with respect to the disorder. A prior work of Xu (2019) used very different methods to show a sharp threshold sequence in the half-space Ising perceptron with Bernoulli disorder. Recent works of Perkins--Xu (2021) and Abbe--Li--Sly (2021) determined the sharp threshold and limiting free energy in a symmetric perceptron model. The results of this paper apply in more general settings, and are based on new "add one constraint" estimates extending Talagrand's estimates for the half-space model (1999, 2011).

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Spectral algorithms for tensor completion

In the tensor completion problem, one seeks to estimate a low-rank tensor based on a random sample of revealed entries. In terms of the required sample size, earlier work revealed a large gap between estimation with unbounded computational resources (using, for instance, tensor nuclear norm minimization) and polynomial-time algorithms. Among the latter, the best statistical guarantees have been proved, for third-order tensors, using the sixth level of the sum-of-squares (SOS) semidefinite programming hierarchy (Barak and Moitra, 2014). However, the SOS approach does not scale well to large problem instances. By contrast, spectral methods --- based on unfolding or matricizing the tensor --- are attractive for their low complexity, but have been believed to require a much larger sample size. This paper presents two main contributions. First, we propose a new unfolding-based method, which outperforms naive ones for symmetric $k$-th order tensors of rank $r$. For this result we make a study of singular space estimation for partially revealed matrices of large aspect ratio, which may be of independent interest. For third-order tensors, our algorithm matches the SOS method in terms of sample size (requiring about $rd^{3/2}$ revealed entries), subject to a worse rank condition ($r\ll d^{3/4}$ rather than $r\ll d^{3/2}$). We complement this result with a different spectral algorithm for third-order tensors in the overcomplete ($r\ge d$) regime. Under a random model, this second approach succeeds in estimating tensors of rank $d\le r \ll d^{3/2}$ from about $rd^{3/2}$ revealed entries.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the asymptotics of dimers on tori

We study asymptotics of the dimer model on large toric graphs. Let $\mathbb L$ be a weighted $\mathbb{Z}^2$-periodic planar graph, and let $\mathbb{Z}^2 E$ be a large-index sublattice of $\mathbb{Z}^2$. For $\mathbb L$ bipartite we show that the dimer partition function on the quotient $\mathbb{L}/(\mathbb{Z}^2 E)$ has the asymptotic expansion $\exp[A f_0 + \text{fsc} + o(1)]$, where $A$ is the area of $\mathbb{L}/(\mathbb{Z}^2 E)$, $f_0$ is the free energy density in the bulk, and $\text{fsc}$ is a finite-size correction term depending only on the conformal shape of the domain together with some parity-type information. Assuming a conjectural condition on the zero locus of the dimer characteristic polynomial, we show that an analogous expansion holds for $\mathbb{L}$ non-bipartite. The functional form of the finite-size correction differs between the two classes, but is universal within each class. Our calculations yield new information concerning the distribution of the number of loops winding around the torus in the associated double-dimer models.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Supercritical minimum mean-weight cycles

We study the weight and length of the minimum mean-weight cycle in the stochastic mean-field distance model, i.e., in the complete graph on $n$ vertices with edges weighted by independent exponential random variables. Mathieu and Wilson showed that the minimum mean-weight cycle exhibits one of two distinct behaviors, according to whether its mean weight is smaller or larger than $1/(ne)$; and that both scenarios occur with positive probability in the limit $n\to\infty$. If the mean weight is $< 1/(ne)$, the length is of constant order. If the mean weight is $> 1/(ne)$, it is concentrated just above $1/(n e)$, and the length diverges with $n$. The analysis of Mathieu--Wilson gives a detailed characterization of the subcritical regime, including the (non-degenerate) limiting distributions of the weight and length, but leaves open the supercritical behavior. We determine the asymptotics for the supercritical regime, showing that with high probability, the minimum mean weight is $(n e)^{-1}[1 + π^2/(2 \log^2 n) + O((\log n)^{-3})]$, and the cycle achieving this minimum has length on the order of $(\log n)^3$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The Hausdorff dimension of the CLE gasket

The conformal loop ensemble $\mathrm{CLE}_κ$ is the canonical conformally invariant probability measure on noncrossing loops in a proper simply connected domain in the complex plane. The parameter $κ$ varies between $8/3$ and $8$; $\mathrm{CLE}_{8/3}$ is empty while $\mathrm {CLE}_8$ is a single space-filling loop. In this work, we study the geometry of the $\mathrm{CLE}$ gasket, the set of points not surrounded by any loop of the $\mathrm{CLE}$. We show that the almost sure Hausdorff dimension of the gasket is bounded from below by $2-(8-κ)(3κ-8)/(32κ)$ when $4<κ<8$. Together with the work of Schramm-Sheffield-Wilson [Comm. Math. Phys. 288 (2009) 43-53] giving the upper bound for all $κ$ and the work of Nacu-Werner [J. Lond. Math. Soc. (2) 83 (2011) 789-809] giving the matching lower bound for $κ\le4$, this completes the determination of the $\mathrm{CLE}_κ$ gasket dimension for all values of $κ$ for which it is defined. The dimension agrees with the prediction of Duplantier-Saleur [Phys. Rev. Lett. 63 (1989) 2536-2537] for the FK gasket.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Factor models on locally tree-like graphs

We consider homogeneous factor models on uniformly sparse graph sequences converging locally to a (unimodular) random tree $T$, and study the existence of the free energy density $ϕ$, the limit of the log-partition function divided by the number of vertices $n$ as $n$ tends to infinity. We provide a new interpolation scheme and use it to prove existence of, and to explicitly compute, the quantity $ϕ$ subject to uniqueness of a relevant Gibbs measure for the factor model on $T$. By way of example we compute $ϕ$ for the independent set (or hard-core) model at low fugacity, for the ferromagnetic Ising model at all parameter values, and for the ferromagnetic Potts model with both weak enough and strong enough interactions. Even beyond uniqueness regimes our interpolation provides useful explicit bounds on $ϕ$. In the regimes in which we establish existence of the limit, we show that it coincides with the Bethe free energy functional evaluated at a suitable fixed point of the belief propagation (Bethe) recursions on $T$. In the special case that $T$ has a Galton-Watson law, this formula coincides with the nonrigorous "Bethe prediction" obtained by statistical physicists using the "replica" or "cavity" methods. Thus our work is a rigorous generalization of these heuristic calculations to the broader class of sparse graph sequences converging locally to trees. We also provide a variational characterization for the Bethe prediction in this general setting, which is of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Maximum independent sets on random regular graphs

We determine the asymptotics of the independence number of the random $d$-regular graph for all $d \ge d_0$. It is highly concentrated, with constant-order fluctuations around $nα_* - c_*\log n$ for explicit constants $α_*(d)$ and $c_*(d)$. Our proof rigorously confirms the one-step replica symmetry breaking heuristics for this problem, and we believe the techniques will be more broadly applicable to the study of other combinatorial properties of random graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Satisfiability threshold for random regular NAE-SAT

We consider the random regular $k$-NAE-SAT problem with $n$ variables each appearing in exactly $d$ clauses. For all $k$ exceeding an absolute constant $k_0$, we establish explicitly the satisfiability threshold $d_*=d_*(k)$. We prove that for $d<d_*$ the problem is satisfiable with high probability while for $d>d_*$ the problem is unsatisfiable with high probability. If the threshold $d_*$ lands exactly on an integer, we show that the problem is satisfiable with probability bounded away from both zero and one. This is the first result to locate the exact satisfiability threshold in a random constraint satisfaction problem exhibiting the condensation phenomenon identified by Krzakala et al. (2007). Our proof verifies the one-step replica symmetry breaking formalism for this model. We expect our methods to be applicable to a broad range of random constraint satisfaction problems and combinatorial problems on random graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Central limit theorem for biased random walk on multi-type Galton-Watson trees

Let T be a rooted supercritical multi-type Galton-Watson (MGW) tree with types coming from a finite alphabet, conditioned to non-extinction. The lambda-biased random walk (X_t, t>=0) on T is the nearest-neighbor random walk which, when at a vertex v with d(v) offspring, moves closer to the root with probability lambda/[lambda+d(v)], and to each of the offspring with probability 1/[lambda+d(v)]. This walk is recurrent for lambda>=rho and transient for 0<lambda<rho, with rho the Perron-Frobenius eigenvalue for the (assumed) irreducible matrix of expected offspring numbers. Subject to finite moments of order p>4 for the offspring distributions, we prove the following quenched CLT for lambda-biased random walk at the critical value lambda=rho: for almost every T, the process |X_{floor(nt)}|/sqrt{n} converges in law as n tends to infinity to a reflected Brownian motion rescaled by an explicit constant. This result was proved under some stronger assumptions by Peres-Zeitouni (2008) for single-type Galton-Watson trees. Following their approach, our proof is based on a new explicit description of a reversing measure for the walk from the point of view of the particle (generalizing the measure constructed in the single-type setting by Peres-Zeitouni), and the construction of appropriate harmonic coordinates. In carrying out this program we prove moment and conductance estimates for MGW trees, which may be of independent interest. In addition, we extend our construction of the reversing measure to a biased random walk with random environment (RWRE) on MGW trees, again at a critical value of the bias. We compare this result against a transience-recurrence criterion for the RWRE generalizing a result of Faraud (2011) for Galton-Watson trees.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Strong path convergence from Loewner driving function convergence

We show that, under mild assumptions on the limiting curve, a sequence of simple chordal planar curves converges uniformly whenever certain Loewner driving functions converge. We extend this result to random curves. The random version applies in particular to random lattice paths that have chordal $\mathrm {SLE}_κ$ as a scaling limit, with $κ<8$ (nonspace-filling). Existing $\mathrm {SLE}_κ$ convergence proofs often begin by showing that the Loewner driving functions of these paths (viewed from $\infty$) converge to Brownian motion. Unfortunately, this is not sufficient, and additional arguments are required to complete the proofs. We show that driving function convergence is sufficient if it can be established for both parametrization directions and a generic observation point.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

The computational hardness of counting in two-spin models on d-regular graphs

The class of two-spin systems contains several important models, including random independent sets and the Ising model of statistical physics. We show that for both the hard-core (independent set) model and the anti-ferromagnetic Ising model with arbitrary external field, it is NP-hard to approximate the partition function or approximately sample from the model on d-regular graphs when the model has non-uniqueness on the d-regular tree. Together with results of Jerrum--Sinclair, Weitz, and Sinclair--Srivastava--Thurley giving FPRAS's for all other two-spin systems except at the uniqueness threshold, this gives an almost complete classification of the computational complexity of two-spin systems on bounded-degree graphs. Our proof establishes that the normalized log-partition function of any two-spin system on bipartite locally tree-like graphs converges to a limiting "free energy density" which coincides with the (non-rigorous) Bethe prediction of statistical physics. We use this result to characterize the local structure of two-spin systems on locally tree-like bipartite expander graphs, which then become the basic gadgets in a randomized reduction to approximate MAX-CUT. Our approach is novel in that it makes no use of the second moment method employed in previous works on these questions.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

The replica symmetric solution for Potts models on d-regular graphs

We provide an explicit formula for the limiting free energy density (log-partition function divided by the number of vertices) for ferromagnetic Potts models on uniformly sparse graph sequences converging locally to the d-regular tree for d even, covering all temperature regimes. This formula coincides with the Bethe free energy functional evaluated at a suitable fixed point of the belief propagation recursion on the d-regular tree, the so-called replica symmetric solution. For uniformly random d-regular graphs we further show that the replica symmetric Bethe formula is an upper bound for the asymptotic free energy for any model with permissive interactions.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Conformally invariant scaling limits in planar critical percolation

This is an introductory account of the emergence of conformal invariance in the scaling limit of planar critical percolation. We give an exposition of Smirnov's theorem (2001) on the conformal invariance of crossing probabilities in site percolation on the triangular lattice. We also give an introductory account of Schramm-Loewner evolutions (SLE(k)), a one-parameter family of conformally invariant random curves discovered by Schramm (2000). The article is organized around the aim of proving the result, due to Smirnov (2001) and to Camia and Newman (2007), that the percolation exploration path converges in the scaling limit to chordal SLE(6). No prior knowledge is assumed beyond some general complex analysis and probability theory.

0 citations0 reviewsNo code linkedOpen access