We consider a synchronous process of particles moving on the vertices of a graph G, introduced by Cooper, McDowell, Radzik, Rivera and Shiraga (2018). Initially, M particles are placed on a vertex of G. In subsequent time steps, all particles that are located on a vertex inhabited by at least two particles jump independently to a neighbour chosen uniformly at random. The process ends at the first step when no vertex is inhabited by more than one particle; we call this (random) time step the dispersion time. In this work we study the case where G is the complete graph on n vertices and the number of particles is M = n/2+α n^{1/2} + o(n^{1/2}), α ∈ ℝ. This choice of M corresponds to the critical window of the process, with respect to the dispersion time. We show that the dispersion time, if rescaled by n^{-1/2}, converges in p-th mean, as n → ∞ and for any p ∈ ℝ, to a continuous and almost surely positive random variable T_α. We find that T_α is the absorption time of a standard logistic branching process, thoroughly investigated by Lambert (2005), and we determine its expectation. In particular, in the middle of the critical window we show that 𝔼[T₀] = π^{3/2}/√7, and furthermore we formulate explicit asymptotics when |α| gets large that quantify the transition into and out of the critical window. We also study the random variable counting the total number of jumps that are performed by the particles until the dispersion time is reached and prove that, if rescaled by nln(n), it converges to 2/7 in probability.

Abstract. We create a novel connection between Boltzmann sampling methods and Devroye’s algorithm to develop highly efficient sampling procedures that generate objects from important combinatorial classes with a given size [Formula: see text] in expected time [Formula: see text]. This performance is best possible and significantly improves the state of the art for samplers of subcritical graph classes (such as cactus graphs, outerplanar graphs, and series-parallel graphs), subcritical substitution-closed classes of permutations, Bienaymé–Galton–Watson trees conditioned on their number of leaves, and several further examples. Our approach allows for this high level of universality, as it applies in general to classes admitting bijective encodings by so-called enriched trees, which are rooted trees with additional structures on the offspring of each node.

Random factor graphs provide a powerful framework for the study of inference problems such as decoding problems or the stochastic block model. Information-theoretically the key quantity of interest is the mutual information between the observed factor graph and the underlying ground truth around which the factor graph was created; in the stochastic block model, this would be the planted partition. The mutual information gauges whether and how well the ground truth can be inferred from the observable data. For a very general model of random factor graphs we verify a formula for the mutual information predicted by physics techniques. As an application we prove a conjecture about low-density generator matrix codes from [Montanari: IEEE Transactions on Information Theory 2005]. Further applications include phase transitions of the stochastic block model and the mixed $k$-spin model from physics.

In the last two decades the study of random instances of constraint satisfaction problems (CSPs) has flourished across several disciplines, including computer science, mathematics and physics. The diversity of the developed methods, on the rigorous and non-rigorous side, has led to major advances regarding both the theoretical as well as the applied viewpoints. The two most popular types of such CSPs are the Erdős-Rényi and the random regular CSPs. Based on a ceteris paribus approach in terms of the density evolution equations known from statistical physics, we focus on a specific prominent class of problems of the latter type, the so-called occupation problems. The regular r-in-k occupation problems resemble a basis of this class. By now, out of these CSPs only the satisfiability threshold - the largest degree for which the problem admits asymptotically a solution - for the 1-in-k occupation problem has been rigorously established. In the present work we take a general approach towards a systematic analysis of occupation problems. In particular, we discover a surprising and explicit connection between the 2-in-k occupation problem satisfiability threshold and the determination of contraction coefficients, an important quantity in information theory measuring the loss of information that occurs when communicating through a noisy channel. We present methods to facilitate the computation of these coefficients and use them to establish explicitly the threshold for the 2-in-k occupation problem for k=4. Based on this result, for general k >= 5 we formulate a conjecture that pins down the exact value of the corresponding coefficient, which, if true, is shown to determine the threshold in all these cases.

Preprocessing a tree for finding the nearest common ancestor of two nodes is a basic tool with multiple applications. Quite a few linear-space constant-time solutions are known and the problem seems to be well-understood. This is however not so clear if we want to design a labeling scheme. In this model, the structure should be distributed: every node receives a distinct binary string, called its label, so that given the labels of two nodes (and no further information about the topology of the tree) we can compute the label of their nearest common ancestor. The goal is to make the labels as short as possible. Alstrup, Gavoille, Kaplan, and Rauhe [Theor. Comput. Syst. 37(3):441–456 2004] showed that O(log n)-bit labels are enough, with a somewhat large constant. More recently, Alstrup, Halvorsen, and Larsen [SODA 2014] refined this to only 2.772 log n, and provided a lower bound of 1.008 log n. We connect the question of designing a labeling scheme for nearest common ancestors to the existence of a tree, called a minor-universal tree, that contains every tree on n nodes as a topological minor. Even though it is not clear if a labeling scheme must be based on such a notion, we argue that all already existing schemes can be reformulated as such. Further, we show that this notion allows us to easily obtain clean and good bounds on the length of the labels. As the main upper bound, we show that 2.318 log n-bit labels are enough. Surprisingly, the notion of a minor-universal tree for binary trees on n nodes has been already used in a different context by Hrubes et al. [CCC 2010], and Young, Chu, and Wong [J. ACM 46(3):416–435, 1999] introduced a very closely related (but not equivalent) notion of a universal tree. On the lower bound side, we show that any minor-universal tree for trees on n nodes must contain at least Ω(n2.174) nodes. This highlights a natural limitation for all approaches based on defining a minor-universal tree. We complement the existential results with a generic transformation that allows us, for any labeling scheme for nearest common ancestors based on a minor-universal tree, to decrease the query time to constant, while increasing the length of the labels only by lower order terms.

We study the fundamental problem of the exact and efficient generation of random values from a finite and discrete probability distribution. Suppose that we are given n distinct events with associated probabilities $$p_1, \dots , p_n$$ p 1 , ⋯ , p n . First, we consider the problem of sampling from the distribution where the i-th event has probability proportional to $$p_i$$ p i . Second, we study the problem of sampling a subset which includes the i-th event independently with probability $$p_i$$ p i . For both problems we present on two different classes of inputs—sorted and general probabilities—efficient data structures consisting of a preprocessing and a query algorithm. Varying the allotted preprocessing time yields a trade-off between preprocessing and query time, which we prove to be asymptotically optimal everywhere.

In this article, we consider a stochastic variant of the so-called Santa Claus problem. The Santa Claus problem is equivalent to the problem of scheduling a set of n jobs on m parallel machines without preemption, so as to maximize the minimum load. We consider the identical machine version of this scheduling problem with the additional restriction that the scheduler has only a guess of the processing times; that is, the processing time of a job is a random variable . We show that there is a critical value ρ ( n,m ) such that if the duration of the jobs is exponentially distributed and the expected values deviate by less than a multiplicative factor of ρ ( n,m ) from each other, then a greedy algorithm has an expected competitive ratio arbitrarily close to one; that is, it performs in expectation almost as good as an algorithm that knows the actual values in advance . On the other hand, if the expected values deviate by more than a multiplicative factor of ρ ( n,m ), then the expected performance is arbitrarily bad for all algorithms.

This paper extends the scenario of the Four Color Theorem in the following way. Let [Formula: see text] be the set of all [Formula: see text]-uniform hypergraphs that can be (linearly) embedded into [Formula: see text]. We investigate lower and upper bounds on the maximum (weak) chromatic number of hypergraphs in [Formula: see text]. For example, we can prove that for [Formula: see text] there are hypergraphs in [Formula: see text] on [Formula: see text] vertices whose chromatic number is [Formula: see text], whereas the chromatic number for [Formula: see text]-vertex hypergraphs in [Formula: see text] is bounded by [Formula: see text] for [Formula: see text].

Random k-SAT is the single most intensely studied example of a random constraint satisfaction problem. But despite substantial progress over the past decade, the threshold for the existence of satisfying assignments is not known precisely for any k≥3. The best current results, based on the second moment method, yield upper and lower bounds that differ by an additive k ⋅ {ln2}/2, a term that is unbounded in k (Achlioptas, Peres: STOC 2003). The basic reason for this gap is the inherent asymmetry of the Boolean values 'true' and 'false' in contrast to the perfect symmetry, e.g., among the various colors in a graph coloring problem. Here we develop a new asymmetric second moment method that allows us to tackle this issue head on for the first time in the theory of random CSPs. This technique enables us to compute the k-SAT threshold up to an additive ln2-1/2+O(1/k) ~0.19. Independently of the rigorous work, physicists have developed a sophisticated but non-rigorous technique called the "cavity method" for the study of random CSPs (Mezard, Parisi, Zecchina: Science~2002). Our result matches the best bound that can be obtained from the so-called "replica symmetric" version of the cavity method, and indeed our proof directly harnesses parts of the physics calculations.

Cuckoo hashing is an efficient technique for creating large hash tables with high space utilization and guaranteed constant access times. There, each item can be placed in a location given by any one out of $k$ different hash functions. In this paper we investigate the random-walk heuristic for inserting in an online fashion new items into the hash table. Provided that $k \ge 3$ and that the number of items in the table is below (but arbitrarily close to) the theoretically achievable load threshold, we show a polylogarithmic bound for the maximum insertion time that holds with probability $1-o(1)$ as the size of the table grows large.

Let Pn denote a graph drawn uniformly at random from the class of all simple planar graphs with n vertices. We show that the maximum degree of a vertex in Pn is with probability 1 − o(1) asymptotically equal to c log n, where c ≈ 2.529 is determined explicitly. A similar result is also true for random 2-connected planar graphs. Our analysis combines two orthogonal methods that complement each other. First, in order to obtain the upper bound, we resort to exact methods, i.e., to generating functions and analytic combinatorics. This allows us to obtain fairly precise asymptotic estimates for the expected number of vertices of any given degree in Pn. On the other hand, for the lower bound we use Boltzmann sampling. In particular, by tracing the execution of an adequate algorithm that generates a random planar graph, we are able to explicitly find vertices of sufficiently high degree in Pn.

We analyze the popular push-pull protocol for spreading a rumor in networks. Initially, a single node knows of a rumor. In each succeeding round, every node chooses a random neighbor, and the two nodes share the rumor if one of them is already aware of it. We present the first theoretical analysis of this protocol on random graphs that have a power law degree distribution with an arbitrary exponent β > 2. Our main findings reveal a striking dichotomy in the performance of the protocol that depends on the exponent of the power law. More specifically, we show that if 2 < β < 3, then the rumor spreads to almost all nodes in Θ(log log n) rounds with high probability. On the other hand, if β > 3, then Ω(log n) rounds are necessary. We also investigate the asynchronous version of the push-pull protocol, where the nodes do not operate in rounds, but exchange information according to a Poisson process with rate 1. Surprisingly, we are able to show that, if 2 < β < 3, the rumor spreads even in constant time, which is much smaller than the typical distance of two nodes. To the best of our knowledge, this is the first result that establishes a gap between the synchronous and the asynchronous protocol.

The best current estimates of the thresholds for the existence of solutions in random constraint satisfaction problems ('CSPs') mostly derive from the first and the second moment method. Yet apart from a very few exceptional cases these methods do not quite yield matching upper and lower bounds. According to deep but non-rigorous arguments from statistical mechanics, this discrepancy is due to a change in the geometry of the set of solutions called condensation that occurs shortly before the actual threshold for the existence of solutions (Krzakala, Montanari, Ricci-Tersenghi, Semerjian, Zdeborova: PNAS~2007). To cope with condensation, physicists have developed a sophisticated but non-rigorous formalism called Survey Propagation (Me-zard, Parisi, Zecchina: Science 2002). This formalism yields precise conjectures on the threshold values of many random CSPs. Here we develop a new Survey Propagation inspired second moment method for the random k-NAESAT problem, which is one of the standard benchmark problems in the theory of random CSPs. This new technique allows us to overcome the barrier posed by condensation rigorously. We prove that the threshold for the existence of solutions in random k-NAESAT is 2k-1ln2-(ln/2 2+1/4)+εk, where |εk| ≤ 2-(1-ok(1))k, thereby verifying the statistical mechanics conjecture for this problem.

A k-uniform hypergraph H = (V, E) is called ℓ-orientable, if there is an assignment of each edge e ∊ E to one of its vertices v G e such that no vertex is assigned more than ℓ edges. Let Hn,m,k be a hypergraph, drawn uniformly at random from the set of all k-uniform hypergraphs with n vertices and m edges. In this paper we establish the threshold for the ℓ-orientability of Hn,m,k for all k ≥ 3 and ℓ > 1, i.e., we determine a critical quantity c*k,ℓ such that with probability 1 − o(1) the graph Hn,cn,k has an ℓ-orientation if c*k,ℓ, but fails doing so if c > c*k,ℓ. Our result has various applications including sharp load thresholds for cuckoo hashing, load balancing with guaranteed maximum load, and massive parallel access to hard disk arrays.

Let Pn be the class of all planar graphs with n labeled vertices, and let Pn be a graph drawn uniformly at random from Pn. In this paper we study the degree sequence of Pn. We show that with probability 1 − o(1) the number of vertices of degree k in Pn is very close to a quantity μkn that we determine explicitly, for all k ≤ c log n and an appropriate c > 0. A similar statement is true for random biconnected planar graphs as well. The main tool in our analysis is a framework that allows us under certain conditions to derive universal results about the degree distribution of random graphs from general classes with structural constraints. In particular, we address so-called critical graph classes, which due to their intricate structure have posed significant technical difficulties in the past.

Broadcasting algorithms are of fundamental importance for distributed systems engineering. In this paper we revisit the classical and well-studied push protocol for message broadcasting and we investigate a faulty version of it. Assuming that initially only one node has some piece of information, at each stage every one of the informed nodes chooses randomly and independently one of its neighbors and passes the message to it with some probability q that is, it fails to do so with probability 1-q. The performance of the push protocol on a fully connected network, where each node is joined by a link to every other node, with q = 1 is very well understood. In particular, Frieze and Grimmett proved that with probability 1-o(1) the push protocol completes the broadcasting of the message within (1 ± ¿) (log2n + ln n) stages, where n is the number of nodes in the network. However, there are no tight bounds for the broadcast time on networks that are significantly sparser than the complete graph. In this work we consider random networks on n nodes, where every edge is present with probability p, independently of every other edge. We show that if p ¿ ¿(n)ln n/n, where ¿(n) is any function that tends to infinity as n grows, then the push protocol with faulty transmissions broadcasts the message within (1± ¿) (log1+qn + 1/q ln n) stages with probability 1-o(1). In other words, in almost every network of density d such that d ¿ ¿(n) ln n, the push protocol broadcasts a message as fast as in a fully connected network and the speed is only affected by the success probability q. This is quite surprising in the sense that the time needed remains essentially unaffected by the fact that most of the links are missing. Our results are accompanied by experimental evaluation.

This work is devoted to the study of the typical structure of a random map. Maps are planar graphs embedded in the plane. We investigate the degree sequences of random maps from families of a certain type, which, among others, includes fundamental map classes like those of biconnected maps, 3-connected maps, and triangulations. In particular, we develop a general framework that allows us to derive relations and exact asymptotic expressions for the expected number of vertices of degree k in random maps from these classes, and also provide accompanying large deviation statements. Extending the work of Gao and Wormald (Combinatorica, 2003) on random general maps, we obtain as results of our framework precise information about the number of vertices of degree k in random biconnected, 3-connected, loopless, and bridgeless maps.

The dynamics of large networks is an important and fascinating problem. Key examples are the Internet, social networks, and the human brain. In this paper we consider a model introduced by DeVille and Peskin [6] for a stochastic pulse-coupled neural network. The key feature and novelty in their approach is that they describe the interactions of a neuronal system as a discrete-state stochastic dynamical network. This idealization has two benefits: it captures essential features of neuronal behavior, and it allows the study of spontaneous synchronization, an important phenomenon in neuronal networks that is well-studied but unfortunately far from being well-understood. In synchronous behavior the firing of one neuron leads to the firing of other neurons, which in turn may set off a chain reaction that often involves a substantial proportion of the neurons. In this paper we rigorously analyze their model. In particular, by applying methods and tools that are frequently used in theoretical computer science, we provide a very precise picture of the dynamics and the evolution of the given system. In particular, we obtain insights into the coexistence of synchronous and asynchronous behavior and the conditions that trigger a “spontaneous” transition from one state to another.

Let C be a class of labeled connected graphs, and let C n be a graph drawn uniformly at random from graphs in C that contain exactly n vertices. Denote by b (ℓ; C n ) the number of blocks (i.e., maximal biconnected subgraphs) of C n that contain exactly ℓ vertices, and let lb (C n ) be the number of vertices in a largest block of C n . We show that under certain general assumptions on C , C n belongs with high probability to one of the following categories: (1) lb (C n ) ∼ cn , for some explicitly given c = c ( C ), and the second largest block is of order n α , where 1 > α = α( C ), or (2) lb (C n ) = O (log n ), that is, all blocks contain at most logarithmically many vertices. Moreover, in both cases we show that the quantity b (ℓ; C n ) is concentrated for all ℓ and we determine its expected value. As a corollary we obtain that the class of planar graphs belongs to category (1). In contrast to that, outerplanar and series-parallel graphs belong to category (2).

Let be the class of simple labeled planar graphs with n vertices, and denote by Pn a graph drawn uniformly at random from this set. Basic properties of Pn were first investigated by Denise, Vasconcellos, and Welsh [7]. Since then, the random planar graph has attracted considerable attention, and is nowadays an important and challenging model for evaluating methods that are developed to study properties of random graphs from classes with structural side constraints. In this paper we study closely the structure of Pn. More precisely, let b(ℓ; Pn) be the number of blocks (i.e. maximal biconnected subgraphs) of Pn that contain exactly ℓ vertices, and let lb(Pn) be the number of vertices in the largest block of Pn. We show that with high probability Pn contains a giant block that includes up to lower order terms cn vertices, where c ≈ 0.959 is an analytically given constant. Moreover, we show that the second largest block contains only (n2/3) vertices, and prove sharp concentration results for b(ℓ; Pn), for all 2 ≤ ℓ ≤ n2/3 (here (.) stands for “up to logarithmic factors”). In fact, we obtain this result as a consequence of a much more general result that we prove in this paper. Let be a class of labeled connected graphs, and let Cn be a graph drawn uniformly at random from graphs in that contain exactly n vertices. Under certain assumptions on , and depending on the behavior of the singularity of the generating function enumerating the elements of , Cn belongs with high probability to one of the following three categories, which differ vastly in complexity. Cn either (1) behaves like a random planar graph, i.e. lb(Cn) ∼ cn, for some analytically given c = c, and the second largest block is of order nα, where 1 > α = α, or (2) lb(Cn) = (log n), i.e., all blocks contain at most logarithmically many vertices, or (3) , for some α = α < 1. Planar graphs belong to category (1). In contrast to that, outerplanar and series-parallel graphs belong to category (2).

Memory management is a fundamental problem in computer architecture and operating systems. We consider a two-level memory system with fast, but small cache and slow, but large main memory. The underlying theoretical problem is known as the paging problem. A sequence of requests to pages has to be served by making each requested page available in the cache. A paging strategy replaces pages in the cache with requested ones. The aim is to minimize the number of page faults that occur whenever a requested page is not in the cache.Experience shows that the paging strategy LEAST-RECENTLY-USED (LRU) usually achieves a factor around 2 to 3 compared to the optimum number of faults. This contrasts the theoretical worst case, in which this factor can be as large as the cache size k.One difficulty in analyzing the paging problem was the lack of an appropriate lower bound for the minimum number of page faults. We address this issue and propose a general lower bound which provides insight into the global structure of a given request sequence. In addition, we derive a characterization for the number of faults incurred by LRU.We give a theoretical explanation why LRU performs well in practice. We classify the set of all request sequences according to certain parameters and prove a bound on the competitive ratio of LRU, which depends on them. This bound varies between 2 and k, i.e., it includes the worst-case, but explains for which sequences LRU achieves constant competitive ratio. The classification is motivated from the structure of request sequences of practical applications: locality of reference and characteristic data access patterns. We argue that this structure yields values around 2 for our bound. Indeed, it is between 2 and 5 in extensive practical experiments.Furthermore, we study the paging problem with variable cache size, which was already considered previously. We show that this approach is not appropriate to explain the usual good performance of LRU. We measure the performance of LRU with the expected competitive ratio E[ALG]/E[OPT] and the expected performance ratio E[ALG]/E[OPT] in a diffuse adversary model and compare both measures. Our analysis yields that the expected competitive ratio gives a misleading answer.