Boolean functions are perhaps the most basic objects of study in theoretical computer
science. They also arise in other areas of mathematics, including combinatorics, statistical …

Although the theory of random graphs is one of the youngest branches of graph theory, in
importance it is second to none. It began with some sporadic papers of Erdős in the 1940s …

Given a monotone graph property $ P $, consider $\mu _p (P) $, the probability that a
random graph with edge probability $ p $ will have $ P $. The function $ d\mu _p (P)/dp $ is …

We report on a case study in programming an early quantum annealer to attack optimization
problems related to operational planning. While a number of studies have looked at the …

For many random constraint satisfaction problems, by now there exist asymptotically tight
estimates of the largest constraint density for which solutions exist. At the same time, for …

We consider the problem of coloring the vertices of a large sparse random graph with a
given number of colors so that no adjacent vertices have the same color. Using the cavity …

The two possible values of the chromatic number of a random graph Page 1 The Two Possible
Values of the Chromatic Number of a Random Graph Dimitris Achlioptas Microsoft Research …

We establish the existence of free energy limits for several sparse random hypergraph
models corresponding to certain combinatorial models on Erdos-Renyi (ER) graph G (N …

Many problems of interest in computer science and information theory can be phrased in
terms of a probability distribution over discrete variables associated to the vertices of a large …

In the bootstrap percolation on the n-dimensional hypercube, in the initial position each of
the 2 n sites is occupied with probability p and empty with probability 1− p, independently of …