Title: Algorithmic Phase Transitions in Constraint Satisfaction Problems
For many Constraint Satisfaction Problems by now we have a good understanding of the largest constraint density for which solutions exist. At the same time, though, all known polynomial-time algorithms for these problems stop finding solutions at much smaller densities. We study this phenomenon by examining how the different sets of solutions evolve as constraints are added. We prove in a precise mathematical sense that, for each problem studied, the barrier faced by algorithms corresponds to a phase transition in that problem's solution-space geometry. Roughly speaking, at some problem-specific critical density, the set of solutions shatters and goes from being a single giant ball to exponentially many, well-separated, tiny pieces. All known polynomial-time algorithms work in the ball regime, but stop as soon as the shattering occurs. Besides giving a geometric view of the solution space of random CSPs our results provide novel constructions of one-way functions.
Joint work with Amin Coja-Oghlan.
Title: Generating Random Graphs with Large Girth
We present a simple and efficient algorithm for randomly generating simple graphs without small cycles. These graphs can be used to design high performance Low-Density Parity-Check (LDPC) codes. For any constant k, a<1/2k(k+3) and m=O(n^{1+a}), our algorithm generates an asymptotically uniform random graph with n vertices, m edges, and girth larger than k in polynomial time. To the best of our knowledge this is the first polynomial algorithm for the problem. Joint work with Andrea Montanari and Amin Saberi.
Title: The Walksat algorithm applied to random CNFs
Walksat is a randomized algorithm for finding a satisfying assignment. In its simplest version, it starts from a random assignment and keeps looking for an unsatisfied clause. As long as one exists it flips the value of a randomly chosen variable occurring in that clause. This algorithm is known to outperform exhaustive search algorithms in the worst case. Applied to random CNFs, it has been known to succeed in linear time up to at least the "pure literal" threshold (Alekhnovich and Ben-Sasson 2004). In this talk I show that Walksat actually succeeds in linear time for densities up to Omega(2^k/k^2). I'm also going to explain why the threshold for Walksat to have a polynomial running time may be 2^k/k.
Joint work with Uriel Feige, Alan Frieze, Michael Krivelevich, and Dan Vilenchik.
Title: Long-range independence and combinatorial optimization with random costs.
Long-range dependence is a key concept in statistical physics arising in connection with phase transition properties of statistical physics models on lattices. In recent years the long-range dependence received more scrutiny as a possible inhibitor for designing fast counting and sampling algorithms for combinatorial models on graphs. In this talk we push this connection further by focusing instead on combinatorial optimization problems. We show that the lack of the long-range dependence can be utilized for designing fast approximation algorithms for combinatorial optimization problems with random costs. We illustrate this idea on the example of maximum weight independent set problem on a bounded degree graph. For the case of exponentially distributed weights and maximum degree three, we show that an arbitrary level of approximation of the objective value can be achieved in polynomial time. In contrast, the maximum size independent set problem is known to be NP-hard to approximate within some constant factor. The difference between the two cost objectives is exactly absence/presence of the long-range order.
Joint work with Theophane Weber.
Title: Counting Independent Sets using BP for Sparse Graphs
We consider the problem of counting number of independent sets in a sparse graph using Belief Propagation (BP). The standard approach based on "correlcation decay" (e.g. work by Dror Weitz (2006) and Bandyopadhyay, Gamarnik (2006) for its logarithm) imply that BP works when the node degree is at most 5 and graph girth being logarithmically large. We ask the following question: is it possible for BP to work for graphs with degree larger than 5 at the expense of girth being somewhat larger? We answer this question in affirmative. This requires us to develop a new method (as correlation decay does not work) based on "loop calculus" introduced by Chertkov and Chernyak (2006). As a consequence of our results, in the case of cubic random graphs we prove that the logarithm of number of independent sets of n nodes scales as C(3) n +O(1) with high probability (with C(3) = 1.545...) if a well-known combinatorical conjecture called 'Shortest Cycle Cover Conjecture' is true. An important consequence of this result is the following unexpected sharpness of result: generically in stat. physics, one expects BP to provide error term upto o(n) (i.e. C(3) n + o(n)) and not O(1) that we obtain.
Joint work with M. Chertkov and D. Shah.
Title: Locked constraint satisfaction problems
I will present the definition and properties of the random `locked' constraint satisfaction problems. When increasing the density of constraints, they display a broad `clustered' phase in which the space of solutions is divided into many isolated points. Compared to the widely studied random K-satisfiability problem the description of the phase diagram is much simpler. On the other hand, and unlike in the K-satisfiability, in the locked problems the whole clustered phase seems intractable for any known algorithm. The locked problems thus serve as (a) new benchmarks of really hard constraint satisfaction problems, (b) set of problems where rigorous understanding should be simpler.