-
作者：Gamarnik, David; Jagannath, Aukosh
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); University of Waterloo
摘要：We consider the algorithmic problem of finding a near ground state (near optimal solution) of a p-spin model. We show that for a class of algorithms broadly defined as Approximate Message Passing (AMP), the presence of the Overlap Gap Property (OGP), appropriately defined, is a barrier. We conjecture that, when p >= 4, the model does indeed exhibit OGP (and prove it for the space of binary solutions). Assuming the validity of this conjecture, as an implication the AMP fails to find near ground...
-
作者：Bhamidi, Shankar; Nam, Danny; Oanh Nguyen; Sly, Allan
作者单位：University of North Carolina; University of North Carolina Chapel Hill; Princeton University
摘要：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 lambda(1) for a Galton-Watson tree is strictly positive if and only if its offspring distribution xi has an exponential tail, that is, Ee(c xi) < infinity for some c > 0, settling a conjecture by Huang and Durrett (2018). On the random graph with degree distributio...
-
作者：Holden, Nina; Peres, Yuval; Zhai, Alex
作者单位：Massachusetts Institute of Technology (MIT); Microsoft; Stanford University
摘要：Given a collection L of n points on a sphere S-n(2) of surface area n, a fair allocation is a partition of the sphere into n cells each of area 1, and each associated with a distinct point of L. We show that if the n points are chosen uniformly at random and the partition is defined by considering a gravitational potential defined by the n points, then the expected distance between a point on the sphere and the associated point of L is O (root log n) which is optimal by a result of Ajtai, Koml...
-
作者：Coupier, David; Saha, Kumarjit; Sarkar, Anish; Viet Chi Tran
作者单位：Universite de Lille; IMT - Institut Mines-Telecom; IMT Nord Europe; Ashoka University; Indian Statistical Institute; Indian Statistical Institute Bangalore; Universite Paris-Est-Creteil-Val-de-Marne (UPEC); Centre National de la Recherche Scientifique (CNRS); Universite Gustave-Eiffel
摘要：The two-dimensional directed spanning forest (DSF) introduced by Baccelli and Bordenave is a planar directed forest whose vertex set is given by a homogeneous Poisson point process N on R-2. If the DSF has direction -e(y), the ancestor h(u) of a vertex u is an element of N is the nearest Poisson point (in the L-2 distance) having strictly larger y-coordinate. This construction induces complex geometrical dependencies. In this paper, we show that the collection of DSF paths, properly scaled, co...
-
作者：Au, Benson; Cebron, Guillaume; Dahlqvist, Antoine; Gabriel, Franck; Male, Camille
作者单位：University of California System; University of California San Diego; Universite de Toulouse; Universite Toulouse III - Paul Sabatier; Universite Federale Toulouse Midi-Pyrenees (ComUE); Institut National des Sciences Appliquees de Toulouse; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Centre National de la Recherche Scientifique (CNRS); University of Sussex; Universite de Bordeaux
摘要：We prove that independent families of permutation invariant random matrices are asymptotically free with amalgamation over the diagonal, both in expectation and in probability, under a uniform boundedness assumption on the operator norm. We can relax the operator norm assumption to an estimate on sums associated to graphs of matrices, further extending the range of applications (e.g., to Wigner matrices with exploding moments and the sparse regime of the Erdos-Renyi model). The result still ho...
-
作者：Rossignol, Raphael
作者单位：Centre National de la Recherche Scientifique (CNRS); Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA)
摘要：Consider a critical Erdos-Renyi random graph: n is the number of vertices, each one of the ((n)(2)) possible edges is kept in the graph independently from the others with probability n(-1) + lambda n (-4/3), lambda being a fixed real number. When n goes to infinity, Addario-Berry, Broutin and Goldschmidt (Probab. Theory Related Fields 152 (2012) 367-406) have shown that the collection of connected components, viewed as suitably normalized measured compact metric spaces, converges in distributi...
-
作者：Beffara, Vincent; Peltola, Eveliina; Wu, Hao
作者单位：Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA); University of Bonn; Tsinghua University
摘要：This article focuses on the characterization of global multiple Schramm-Loewner evolutions (SLE). The chordal SLE describes the scaling limit of a single interface in various critical lattice models with Dobrushin boundary conditions, and similarly, global multiple SLEs describe scaling limits of collections of interfaces in critical lattice models with alternating boundary conditions. In this article, we give a minimal amount of characterizing properties for the global multiple SLEs: we prove...
-
作者：Cannizzaro, Giuseppe; Erhard, Dirk; Schonbauer, Philipp
作者单位：University of Warwick; Universidade Federal da Bahia; Imperial College London
摘要：In this work we focus on the two-dimensional anisotropic KPZ (aKPZ) equation, which is formally given by partial derivative(t)h = v/2 Delta h + lambda(partial derivative(1)h)(2) - (partial derivative(2)h)(2)) + v(1/2)xi, where xi denotes a noise which is white in both space and time, and lambda and nu are positive constants. Due to the wild oscillations of the noise and the quadratic nonlinearity, the previous equation is classically ill posed. It is not possible to linearise it via the Cole-H...
-
作者：Cryan, Mary; Guo, Heng; Mousa, Giorgos
作者单位：University of Edinburgh
摘要：We show that the modified log-Sobolev constant for a natural Markov chain which converges to an r -homogeneous strongly log-concave distribution is at least 1/r. Applications include a sharp mixing time bound for the bases-exchange walk for matroids, and a concentration bound for Lipschitz functions over these distributions.
-
作者：Armstrong, Scott; Serfaty, Sylvia
作者单位：New York University
摘要：We study Coulomb gases in any dimension d >= 2 and in a broad temperature regime. We prove local laws on the energy, separation and number of points down to the microscopic scale. These yield the existence of limiting point processes after extraction, generalizing the Ginibre point process for arbitrary temperature and dimension. The local laws come together with a quantitative expansion of the free energy with a new explicit error rate in the case of a uniform background density. These estima...
