Frozen 1-RSB structure of the symmetric Ising perceptron

We prove, under an assumption on the critical points of a real-valued function, that the symmetric Ising perceptron exhibits the ‘frozen 1-RSB’ structure conjectured by Krauth and Mézard in the physics literature; that is, typical solutions of the model lie in clusters of vanishing entropy density. Moreover, we prove this in a very strong form conjectured by Huang, Wong, and Kabashima: a typical solution of the model is isolated with high probability and the Hamming distance to all other solutions is linear in the dimension. The frozen 1-RSB scenario is part of a recent and intriguing explanation of the performance of learning algorithms by Baldassi, Ingrosso, Lucibello, Saglietti, and Zecchina. We prove this structural result by comparing the symmetric Ising perceptron model to a planted model and proving a comparison result between the two models. Our main technical tool towards this comparison is an inductive argument for the concentration of the logarithm of number of solutions in the model.     

Monte-Carlo approximations for 2d Navier-Stokes equations with measure initial data

We are interested in proving Monte-Carlo approximations for 2d Navier-Stokes equations with initial data u ₀ belonging to the Lorentz space L ^2,∞ and such that curl u ₀ is a finite measure. Giga, Miyakawaand Osada [7] proved that a solution u exists and that u=K* curl u, where K is the Biot-Savartkernel and v = curl u is solution of a nonlinear equation in dimension one, called the vortex equation. In this paper, we approximate a solution v of this vortex equationby a stochastic interacting particlesystem and deduce a Monte-Carlo approximation for a solution of the Navier-Stokesequation. That gives in this case a pathwise proofof the vortex algorithm introducedby Chorin and consequently generalizes the works ofMarchioro-Pulvirenti [12] and Méléardv [15] obtained in the case of a vortex equation with bounded density initial data. Received: 6 October 1999 / Revised version: 15 September 2000 / Published online: 9 October 2001     

Approximate Ultrametricity for Random Measures and Applications to Spin Glasses

In this documentname, we introduce a notion called “approximate ultrametricity,” which encapsulates the phenomenology of a sequence of random probability measures having supports that behave like ultrametric spaces insofar as they decompose into nested balls. We provide a sufficient condition for a sequence of random probability measures on the unit ball of an infinite‐dimensional separable Hilbert space to admit such a decomposition, whose elements we call clusters. We also characterize the laws of the measures of the clusters by showing that they converge in law to the weights of a Ruelle probability cascade. These results apply to a large class of classical models in mean field spin glasses. We illustrate the notion of approximate ultrametricity by proving a conjecture of Talagrand regarding mixed p‐spin glasses that is known to imply a prediction of Dotsenko‐Franz‐Mézard. © 2017 Wiley Periodicals, Inc.     

An efficient local search method for random 3-satisfiability

We report on some exceptionally good results in the solution of randomly generated 3-satisfiability instances using the “record-to-record travel (RRT)” local search method. When this simple, but less-studied algorithm is applied to random one-million variable instances from the problem's satisfiable phase, it seems to find satisfying truth assignments almost always in linear time, with the coefficient of linearity depending on the ratio α of clauses to variables in the generated instances. RRT has a parameter for tuning “greediness”. By lessening greediness, the linear time phase can be extended up to very close to the satisfiability threshold α_c. Such linear time complexity is typical for random-walk based local search methods for small values of α. Previously, however, it has been suspected that these methods necessarily lose their time linearity far below the satisfiability threshold. The only previously introduced algorithm reported to have nearly linear time complexity also close to the satisfiability threshold is the survey propagation (SP) algorithm. However, SP is not a local search method and is more complicated to implement than RRT. Comparative experiments with the WalkSAT local search algorithm show behavior somewhat similar to RRT, but with the linear time phase not extending quite as close to the satisfiability threshold.     

A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae

Experiments on solvingr-SAT random formulae have provided evidence of a satisfiability threshold phenomenon with respect to the ratio of the number of clauses to the number of variables of formulae. Presently, only the threshold of 2-SAT formulae has been proved to exist and has been computed to be equal to 1. For 3-SAT formulae and more generally forr-SAT formulae, lower and upper bounds of the threshold have been established. The best established bounds concern 3-SAT. For an observed threshold of about 4.25, the best lower bound is 3.003 and the best upper bound 4.76. In this paper we establish a general upper bound of the threshold forr-SAT formulae giving a value for 3-SAT of 4.64, significantly improving the previous best upper bound. For this we have defined a more restrictive structure than a satisfying truth assignment for characterizing the satisfiability of a SAT formula which we have called negatively prime solution (NPS). By merely applying the first moment method to negatively prime solutions of a randomr-SAT formula we obtain our bound.     

Projective‐Planar Graphs with no K3, 4‐Minor. II

The authors previously published an iterative process to generate a class of projective‐planar K_{3, 4}‐free graphs called “patch graphs.” They also showed that any simple, almost 4‐connected, nonplanar, and projective‐planar graph that is K_{3, 4}‐free is a subgraph of a patch graph. In this article, we describe a simpler and more natural class of cubic K_{3, 4}‐free projective‐planar graphs that we call Möbius hyperladders. Furthermore, every simple, almost 4‐connected, nonplanar, and projective‐planar graph that is K_{3, 4}‐free is a minor of a Möbius hyperladder. As applications of these structures we determine the page number of patch graphs and of Möbius hyperladders.     

The 3-XORSAT thresholdLe seuil de 3-XORSAT

We prove the existence of a threshold phenomenon regarding the random 3-XORSAT problem (or more generally k-XORSAT). We provide the value of the threshold as the solution of two transcendental equations. These results confirm rigorously those obtained by physicists using the one-step replica symmetry breaking method and thus give for the first time the proof of the validity of this method for a problem of the class of satisfiability problems. To cite this article: O. Dubois, J. Mandler, C. R. Acad. Sci. Paris, Ser. I 335 (2002) 963–966.     

Stochastic control with exit time and constraints,application to small time attainability of sets

We study the existence of a solution of controlled stochastic differential equations remaining in a given set of constraints at any time smaller than the exit time of a given open set. We also investigate the small time attainability of a given closed set K, i.e., the property that, for all arbitrary small time horizon T and for all initial condition in a sufficiently small neighborhood of K, there exists a solution to the controlled stochastic differential equation which reaches K before T.     

Delaying satisfiability for random 2SAT

Let (C₁,C′_(*)),(C₂,C′_(*)),…,(C _m,C′_(*)) be a sequence of ordered pairs of 2CNF clauses chosen uniformly at random (with replacement) from the set of all 4 \begin{align*}\binom{n}{2}\end{align*} clauses on n variables. Choosing exactly one clause from each pair defines a probability distribution over 2CNF formulas. The choice at each step must be made on‐line, without backtracking, but may depend on the clauses chosen previously. We show that there exists an on‐line choice algorithm in the above process which results whp in a satisfiable 2CNF formula as long as m/n ≤ (1000/999)^1/4. This contrasts with the well‐known fact that a random m ‐clause formula constructed without the choice of two clauses at each step is unsatisfiable whp whenever m/n > 1. Thus the choice algorithm is able to delay satisfiability of a random 2CNF formula beyond the classical satisfiability threshold. Choice processes of this kind in random structures are known as “Achlioptas processes.” This paper joins a series of previous results studying Achlioptas processes in different settings, such as delaying the appearance of a giant component or a Hamilton cycle in a random graph. In addition to the on‐line setting above, we also consider an off‐line version in which all m clause‐pairs are presented in advance, and the algorithm chooses one clause from each pair with knowledge of all pairs. For the off‐line setting, we show that the two‐choice satisfiability threshold for k ‐SAT for any fixed k coincides with the standard satisfiability threshold for random 2k ‐SAT.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Conjugate gradient versus contraction mapping

The solution of linear equationsCu ⁰+b=0 foru ⁰ is considered here, withC a positive-definite and self-adjoint operator. Such equations arise when solving quadratic optimization problems and (for example) when solving partial differential equations using finite-difference methods. A standard solution technique is to approximateC by an operatorK which is easy to invert and then to construct an algorithm of the contraction-mapping type to useK ^–1 iteratively to help solve the original equation. Such algorithms have long been used for solving equations of this type. The aim of the paper is to show that, for eachK, a little-known generalization of the usual conjugate-gradient algorithm has advantages over the corresponding contraction-mapping algorithm in that it has better convergence properties. In addition, it is not significantly more difficult to implement. IfK is a good approximation toC, the resulting generalized conjugate-gradient algorithm is more effective than the usual conjugate-gradient algorithm.The computed results presented in Section 4 were obtained by P. Bluett while a research student at Imperial College.     

Sur le caractère d’invariant Stablement Birationnel d'un Groupe de Tate–Shafarevich

Using the Tate–Poitou duality, Sansuc proved that the group III¹(K, G) is stably K-birational invariant of G for a connected linear algebraic group defined over a number field K. In this paper, we consider the case where K is a function field, in one variable over a PAC field (K is a “good” field in sense Colliot–Thélène and Kunyavskii). We show that the group III¹(K, G) is stably K-birational invariant when G is a connected reductive K-group. Since we no longer have the Tate–Poitou duality at our disposition, we use the flasque resolutions of Colliot–Thélène and Sansuc.

En utilisant la dualité de Tate–Poitou, Sansuc a établi le caractère d'invariant stablement K-birationnel du groupe III¹(K, G) pour un groupe algébrique linéaire connexe G défini sur un corps de nombres K. Dans cet article, nous considérons le cas où K est un corps de fonctions en une variable sur un corps PAC (K est un “bon” corps au sens de Colliot–Thélène et Kunyavskii). Nous montrons le caractère d'invariant stablement K-birationnel du groupe III¹(K, G) pour un K-groupe réductif connexe G. Comme nous n'avons plus à notre disposition la dualité de Tate–Poitou, nous devons utiliser les résolutions flasques de Colliot–Thélène et Sansuc.     

On the Intersection Number of Matchings and Minimum Weight Perfect Matchings of Multicolored Point Sets

Let P and Q be disjoint point sets with 2r and 2s elements respectively, and M₁ and M₂ be their minimum weight perfect matchings (with respect to edge lengths). We prove that the edges of M₁ and M₂ intersect at most |M₁|+|M₂|−1 times. This bound is tight. We also prove that P and Q have perfect matchings (not necessarily of minimum weight) such that their edges intersect at most min{r,s} times. This bound is also sharp. Supported by PAPIIT(UNAM) of México, Proyecto IN110802 Supported by FAI-UASLP and by CONACYT of México, Proyecto 32168-E Supported by CONACYT of México, Proyecto 37540-A     

Tail bounds for occupancy and the satisfiability threshold conjecture

The classical occupancy problem is concerned with studying the number of empty bins resulting from a random allocation of m balls to n bins. We provide a series of tail bounds on the distribution of the number of empty bins. These tail bounds should find application in randomized algorithms and probabilistic analysis. Our motivating application is the following well-known conjecture on threshold phenomenon for the satisfiability problem. Consider random 3-SAT formulas with cn clauses over n variables, where each clause is chosen uniformly and independently from the space of all clauses of size 3. It has been conjectured that there is a sharp threshold for satisfiability at c* ≈? 4.2. We provide a strong upper bound on the value of c*, showing that for c > 4.758 a random 3-SAT formula is unsatisfiable with high probability. This result is based on a structural property, possibly of independent interest, whose proof needs several applications of the occupancy tail bounds.     

The ζ(2) limit in the random assignment problem

The random assignment (or bipartite matching) problem asks about A_n=min_π ∑c(i, π(i)), where (c(i, j)) is a n×n matrix with i.i.d. entries, say with exponential(1) distribution, and the minimum is over permutations π. Mézard and Parisi (1987) used the replica method from statistical physics to argue nonrigorously that EA_n→ζ(2)=π²/6. Aldous (1992) identified the limit in terms of a matching problem on a limit infinite tree. Here we construct the optimal matching on the infinite tree. This yields a rigorous proof of the ζ(2) limit and of the conjectured limit distribution of edge‐costs and their rank‐orders in the optimal matching. It also yields the asymptotic essential uniqueness property: every almost‐optimal matching coincides with the optimal matching except on a small proportion of edges. ©2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 381–418, 2001     

On the solution‐space geometry of random constraint satisfaction problems

For various random constraint satisfaction problems there is a significant gap between the largest constraint density for which solutions exist and the largest density for which any polynomial time algorithm is known to find solutions. Examples of this phenomenon include random k‐SAT, random graph coloring, and a number of other random constraint satisfaction problems. To understand this gap, we study the structure of the solution space of random k‐SAT (i.e., the set of all satisfying assignments viewed as a subgraph of the Hamming cube). We prove that for densities well below the satisfiability threshold, the solution space decomposes into an exponential number of connected components and give quantitative bounds for the diameter, volume, and number.© 2010 Wiley Periodicals, Inc. Random Struct. Alg., 38, 251–268, 2011     

Approximating nonstationaryPh(t)/M(t)/s/c queueing systems

Nonstationary phase processes are defined and a surrogate distribution approximation (SDA) method for analyzing transient and nonstationary queueing systems with nonstationary phase arrival processes is presented. Regardless of system capacityc, the SDA method requires the numerical solution of only 6K differential equations, whereK is the number of phases in the arrival process, compared to theK(c+1) Kolmogorov forward equations required for the classical method of solution. Time-dependent approximations of mean and variance of the number of entities in the system and the number of busy servers are obtained. Empirical test results over a wide range of systems indicate the SDA is quite accurate.This research was partially funded by National Science Foundation grant ECS-8404409.     

Painlevé Classification of All Semilinear Partial Differential Equations of the Second Order. II. Parabolic and Higher Dimensional Equations

This paper extends the work of the previous paper (I) on the Painlevé classification of second-order semilinear partial differential equations to the case of parabolic equations in two independent variables, u_xx = F(x, y, u, u_x, u_y), and irreducible equations in three or more independent variables of the form, Σ_ijR_ij (x₁,…, x_n)u,_ij = F(x₁,…, x_n; u,₁,…, u,_n). In each case, F is assumed to be rational in u and its first derivatives and no other simplifying assumptions are made. In addition to the 22 hyperbolic equations found in paper I, we find 10 equivalence classes of parabolic equations with the Painlevé property, denoted PS-I, PS-I1,…, PS-X, equation PS-II being a generalization of Burgers' equation denoted the Forsyth-Burgers equation, and 13 higher-dimensional Painlevé equations, denoted GS-I, GS-II,…, GS-XIII. The lists are complete up to the equivalence relation of Möbius transformations in u and arbitrary changes of the independent variables. In order to avoid repetition, the proofs are sketched very briefly in cases where they closely resemble those for the corresponding hyperbolic problem. Every equation is solved by transforming to a linear partial differential equation, from which it follows that there are no non trivial soliton equations among the two classes of Painlevé equations treated in this paper.     

Field induced aggregation in electrorheological suspension: kernel form and self similar solutions

Within the framework of the study of the fibrillation mechanism in an electrorheological (ER) suspension, this work presents a comparison between the self similar solutions when the kernel is K_i,j ~ (i⁻¹ + j⁻¹) and the behaviour of the chains growth. Till now, the field induced chains formation has only been studied by numerical or experimental methods. The work of Fournier and Lauren?ot (Communications in Mathematical Physics 256 2005) on the Smoluchowski’s equation allows us to present an analytical solution for the field induced pearl chains in a colloidal ER suspension. René Limage: Chercheur indépendant, dipl?mé de l’Université de Liége.     

On a class of nonlocal parabolic equations

We consider a boundary value problem for parabolic equations with nonlocal nonlinearity of such a form that favorably differs from other equations in that it leads to partial differential equations that have important properties of ordinary differential equations. Local solvability and uniqueness theorems are proved, and an analog of the Painlevé singular nonfixed points theorem is proved. In this case, there is an alternative—either a solution exists for all t ≥ 0 or it goes to infinity in a finite time t = T (blowup mode). Sufficient conditions for the existence of a blowup mode are given.