A continuous–discontinuous second‐order transition in the satisfiability of random Horn‐SAT formulas

We compute the probability of satisfiability of a class of random Horn‐SAT formulae, motivated by a connection with the nonemptiness problem of finite tree automata. In particular, when the maximum clause length is three, this model displays a curve in its parameter space, along which the probability of satisfiability is discontinuous, ending in a second‐order phase transition where it is continuous but its derivative diverges. This is the first case in which a phase transition of this type has been rigorously established for a random constraint satisfaction problem. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Optimality Conditions for Linear-Convex Optimal Control Problems with Mixed Constraints

Journal of Optimization Theory and Applications - In this paper, we provide sufficient optimality conditions for convex optimal control problems with mixed constraints. On one hand, the data...     

Inference and phase transitions in the detection of modules in sparse networks

We present an asymptotically exact analysis of the problem of detecting communities in sparse random networks generated by stochastic block models. Using the cavity method of statistical physics and its relationship to belief propagation, we unveil a phase transition from a regime where we can infer the correct group assignments of the nodes to one where these groups are undetectable. Our approach yields an optimal inference algorithm for detecting modules, including both assortative and disassortative functional modules, assessing their significance, and learning the parameters of the underlying block model. Our algorithm is scalable and applicable to real-world networks, as long as they are well described by the block model.     

Random graph models for dynamic networks

Recent theoretical work on the modeling of network structure has focused primarily on networks that are static and unchanging, but many real-world networks change their structure over time. There exist natural generalizations to the dynamic case of many static network models, including the classic random graph, the configuration model, and the stochastic block model, where one assumes that the appearance and disappearance of edges are governed by continuous-time Markov processes with rate parameters that can depend on properties of the nodes. Here we give an introduction to this class of models, showing for instance how one can compute their equilibrium properties. We also demonstrate their use in data analysis and statistical inference, giving efficient algorithms for fitting them to observed network data using the method of maximum likelihood. This allows us, for example, to estimate the time constants of network evolution or infer community structure from temporal network data using cues embedded both in the probabilities over time that node pairs are connected by edges and in the characteristic dynamics of edge appearance and disappearance. We illustrate these methods with a selection of applications, both to computer-generated test networks and real-world examples.     

Group representations that resist random sampling

We show that there exists a family of groups G_n and nontrivial irreducible representations ρ_n such that, for any constant t, the average of ρ_n over t uniformly random elements has operator norm 1 with probability approaching 1 as . More quantitatively, we show that there exist families of finite groups for which random elements are required to bound the norm of a typical representation below 1. This settles a conjecture of A. Wigderson. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 605–614, 2015     

An Analog Characterization of the Grzegorczyk Hierarchy

We study a restricted version of Shannon's general purpose analog computer in which we only allow the machine to solve linear differential equations. We show that if this computer is allowed to sense inequalities in a differentiable way, then it can compute exactly the elementary functions, the smallest known recursive class closed under time and space complexity. Furthermore, we show that if the machine has access to a function f(x) with a suitable growth as x goes to infinity, then it can compute functions on any given level of the Grzegorczyk hierarchy. More precisely, we show that the model contains exactly the nth level of the Grzegorczyk hierarchy if it is allowed to solve n−3 non-linear differential equations of a certain kind. Therefore, we claim that, at least in this region of the complexity hierarchy, there is a close connection between analog complexity classes, the dynamical systems that compute them, and classical sets of subrecursive functions.     

Legendre Transform and Applications to Finite and Infinite Optimization

We investigate convex constrained nonlinear optimization problems and optimal control with convex state constraints in the light of the so-called Legendre transform. We use this change of coordinate to propose a gradient-like algorithm for mathematical programs, which can be seen as a search method along geodesics. We also use the Legendre transform to study the value function of a state constrained Mayer problem and we show that it can be characterized as the unique viscosity solution of the Hamilton-Jacobi-Bellman equation.     

Height Representation,Critical Exponents,and Ergodicity in the Four-State Triangular Potts Antiferromagnet

We study the four-state antiferromagnetic Potts model on the triangular lattice. We show that the model has six types of defects which diffuse and annihilate according to certain conservation laws consistent with their having a vector-valued topological charge. Using the properties of these defects, we deduce a (2+2)-dimensional height representation for the model and hence show that the model is equivalent to the three-state Potts antiferromagnet on the Kagomé lattice and to bond-coloring models on the triangular and honeycomb lattices. We also calculate critical exponents for the ground-state ensemble of the model. We find that the exponents governing the spin–spin correlation function and spin fluctuations violate the Fisher scaling law because of constraints on path length which increase the effective wavelength of the spin operator on the height lattice. We confirm our predictions by extensive Monte Carlo simulations of the model using the Wang–Swendsen–Kotecký cluster algorithm. Although this algorithm is not ergodic on lattices with toroidal boundary conditions, we prove that it is ergodic on lattices whose topology has no noncontractible loops of infinite order, such as the projective plane. To guard against biases introduced by lack of ergodicity, we perform our simulations on both the torus and the projective plane.