107 research outputs found
Local Approximations of the Independent Set Polynomial
No full textThe independent set polynomial of a graph has one variable for each vertex and one monomial for each independent set, comprising the product of the corresponding variables. Given a graph G on n vertices and a vector p ∈ [0,1)ⁿ, a central problem in statistical mechanics is determining whether the independent set polynomial of G is non-vanishing in the polydisk of p, i.e., whether |Z_G(x)| > 0 for every x ∈ ℂⁿ such that |x_i| ≤ p_i. Remarkably, when this holds, Z_G(-p) is a lower bound for the avoidance probability when G is a dependency graph for n events whose probabilities form vector p. A local sufficient condition for |Z_G| > 0 in the polydisk of p is the Lovász Local Lemma (LLL).
In this work we derive several new results on the efficient evaluation and bounding of Z_G. Our starting point is a monotone mapping from subgraphs of G to truncations of the tree of self-avoiding walks of G. Using this mapping our first result is a local upper bound for Z(-p), similar in spirit to the local lower bound for Z(-p) provided by the LLL. Next, using this mapping, we show that when G is chordal, Z_G can be computed exactly and in linear time on the entire complex plane, implying perfect sampling for the hard-core model on chordal graphs. We also revisit the task of bounding Z(-p) from below, i.e., the LLL setting, and derive four new lower bounds of increasing sophistication. Already our simplest (and weakest) bound yields a strict improvement of the famous asymmetric LLL, i.e., a strict relaxation of the inequalities of the asymmetric LLL without any further assumptions. This new asymmetric local lemma is sharp enough to recover Shearer’s optimal bound in terms of the maximum degree Δ(G). We also apply our more sophisticated bounds to estimate the zero-free region of the hard-core model on the triangular lattice (hard hexagons model)
Algorithmic Improvements of the Lovász Local Lemma via Cluster Expansion
No full textThe Lovasz Local Lemma (LLL) is a powerful tool that can be used to prove that an object having none of a set of bad properties exists, using the probabilistic method. In many applications of the LLL it is also desirable to explicitly construct the combinatorial object. Recently it was shown that this is possible using a randomized algorithm in the full asymmetric LLL setting [R. Moser and G. Tardos, 2010]. A strengthening of the LLL for the case of dense local neighborhoods proved in [R. Bissacot et al., 2010] was recently also made constructive in [W. Pegden, 2011]. In another recent work [B. Haupler, B. Saha, A. Srinivasan, 2010], it was proved that the algorithm of Moser and Tardos is still efficient even when the number of events is exponential. Here we prove that these last two contributions can be combined to yield a new version of the LLL
LIPIcs, Volume 145, APPROX/RANDOM'19, Complete Volume
No full textLIPIcs, Volume 145, APPROX/RANDOM'19, Complete Volum
Stochastic Control via Entropy Compression
No full textConsider an agent trying to bring a system to an acceptable state by repeated probabilistic action. Several recent works on algorithmizations of the Lovász Local Lemma (LLL) can be seen as establishing sufficient conditions for the agent to succeed. Here we study whether such stochastic control is also possible in a noisy environment, where both the process of state-observation and the process of state-evolution are subject to adversarial perturbation (noise). The introduction of noise causes the tools developed for LLL algorithmization to break down since the key LLL ingredient, the sparsity of the causality (dependence) relationship, no longer holds. To overcome this challenge we develop a new analysis where entropy plays a central role, both to measure the rate at which progress towards an acceptable state is made and the rate at which noise undoes this progress. The end result is a sufficient condition that allows a smooth tradeoff between the intensity of the noise and the amenability of the system, recovering an asymmetric LLL condition in the noiseless case
Front Matter, Table of Contents, Preface, Conference Organization
No full textFront Matter, Table of Contents, Preface, Conference Organizatio
On the Solution-Space Geometry of Random Constraint Satisfaction Problems
No full textFor a number of random constraint satisfaction problems, such as random k-SAT and random graph/hypergraph coloring, there are very good estimates of the largest constraint density for which solutions exist. Yet, all known polynomial-time algorithms for these problems fail to find solutions even at much lower densities. To understand the origin of this gap we study how the structure of the space of solutions evolves in such problems as constraints are added. In particular, we prove that much before solutions disappear, they organize into an exponential number of clusters, each of which is relatively small and far apart from all other clusters. Moreover, inside each cluster most variables are frozen, i.e., take only one value. The existence of such frozen variables gives a satisfying intuitive explanation for the failure of the polynomial-time algorithms analyzed so far. At the same time, our results establish rigorously one of the two main hypotheses underlying Survey Propagation, a heuristic introduced by physicists in recent years that appears to perform extraordinarily well on random constraint satisfaction problems. Copyright 2006 ACM
RANDOM FORMULAS HAVE FROZEN VARIABLES
No full textFor a large number of random constraint satisfaction problems, such as random k-SAT and random graph and hypergraph coloring, there exist very good estimates of the largest constraint density for which solutions exist. All known polynomial-time algorithms for these problems, though, fail to find solutions even at much lower densities. To understand the origin of this gap one can study how the structure of the space of solutions evolves in such problems as constraints are added. In particular, it is known that much before solutions disappear, they organize into an exponential number of clusters, each of which is relatively small and far apart from all other clusters. Here we further prove that inside every cluster the vast majority of variables are frozen, i.e., take only one value. The existence of such frozen variables gives a satisfying intuitive explanation for the failure of the polynomial-time algorithms analyzed so far. At the same time, our results lend support to one of the two main hypotheses underlying Survey Propagation, a heuristic introduced by physicists in recent years that appears to perform extraordinarily well on random constraint satisfaction problems
Recommended from our members
Unsatisfiability Bounds for Random Constraint Satisfaction Problems from an Energetic Interpolation Method
No full textThe interpolation method, originally developed in statistical physics, transforms distributions of random Constraint Satisfaction Problems (CSPs) to distributions of much simpler problems while bounding the change in a number of associated statistical quantities along the transformation path. By now, it is known that, in principle, the method can yield rigorous unsatisfiability results if one ``plugs in an appropriate functional distribution'' to the derived expressions. A drawback of the method is that identifying the appropriate distribution leads to major analytical challenges as the relevant distributions are, in fact, infinite dimensional objects. We develop a variant of the interpolation method for random CSPs on arbitrary sparse degree distributions which trades accuracy for tractability. In particular, our bounds only require the solution of a 1-dimensional optimization problem (which typically turns out to be very easy) and as such can be used to compute explicit rigorous unsatisfiability bounds. We use this new method to analyze the performance of a number of algorithms on random 3-CNF formulas with n variables and m=rn clauses. A long series of papers analyzing so-called ``myopic'' algorithms has provided a sequence of lower bounds for the satisfiability threshold, which is widely believed to be r~4.26. Indeed, for each myopic algorithm A it is known that there exists an algorithm-specific clause-density, r_A, such that if r2.78 and the same is true for generalized unit clause for all r>3.1. Our results imply exponential lower bounds for many other myopic algorithms for densities similarly close to the corresponding r_A
Database-friendly random projections: Johnson-Lindenstrauss with binary coins
No full textAbstractA classic result of Johnson and Lindenstrauss asserts that any set of n points in d-dimensional Euclidean space can be embedded into k-dimensional Euclidean space—where k is logarithmic in n and independent of d—so that all pairwise distances are maintained within an arbitrarily small factor. All known constructions of such embeddings involve projecting the n points onto a spherically random k-dimensional hyperplane through the origin. We give two constructions of such embeddings with the property that all elements of the projection matrix belong in {−1,0,+1}. Such constructions are particularly well suited for database environments, as the computation of the embedding reduces to evaluating a single aggregate over k random partitions of the attributes
Malleable Scheduling Beyond Identical Machines
No full textIn malleable job scheduling, jobs can be executed simultaneously on multiple machines with the processing time depending on the number of allocated machines. Jobs are required to be executed non-preemptively and in unison, in the sense that they occupy, during their execution, the same time interval over all the machines of the allocated set. In this work, we study generalizations of malleable job scheduling inspired by standard scheduling on unrelated machines. Specifically, we introduce a general model of malleable job scheduling, where each machine has a (possibly different) speed for each job, and the processing time of a job j on a set of allocated machines S depends on the total speed of S for j. For machines with unrelated speeds, we show that the optimal makespan cannot be approximated within a factor less than e/(e-1), unless P = NP. On the positive side, we present polynomial-time algorithms with approximation ratios 2e/(e-1) for machines with unrelated speeds, 3 for machines with uniform speeds, and 7/3 for restricted assignments on identical machines. Our algorithms are based on deterministic LP rounding and result in sparse schedules, in the sense that each machine shares at most one job with other machines. We also prove lower bounds on the integrality gap of 1+phi for unrelated speeds (phi is the golden ratio) and 2 for uniform speeds and restricted assignments. To indicate the generality of our approach, we show that it also yields constant factor approximation algorithms (i) for minimizing the sum of weighted completion times; and (ii) a variant where we determine the effective speed of a set of allocated machines based on the L_p norm of their speeds
- …
