Abstracts

Dimitris Achlioptas, Microsoft Research

What's up with random 3-SAT

Consider a random 3-SAT formula on n variables, formed by repeatedly adding clauses as follows: pick 3 variables at random, negate each one with probability 1/2, and take the conjunction. Formulas constructed in this manner have a number of exciting properties, especially when the number of clauses, m, is linear in n. The most well-known such property has led to the satisfiability threshold conjecture asserting that there exists a constant r such that for any t>0, if m=(r-t)*n the resulting formula is almost surely satisfiable, while if m=(r+t)*n the resulting formula is almost surely unsatisfiable.

In the last 10 years this conjecture has received a fair amount of attention in computer science, mathematics and statistical physics. It has motivated a number of related notions and has brought to light some rather unexpected connections. The talk will attempt to give a bird's eye view of random 3-SAT, leading to the current state of the art. No prior knowledge of random formulas, thresholds etc. will be assumed.
 

David Aldous, University of California, Berkeley

The zeta(2) limit in the random assignment problem

The random assignment (or bipartite matching) problem asks about $A_n = \min_\pi \sum_{i=1}^n c_{i,\pi(i)}$, where $(c_{ij})$ is a $n \times n$ matrix with i.i.d. entries, say with exponential(1) distribution, and the minimum is over permutations $\pi$. Mézard and Parisi (1987) used the replica method from statistical physics to argue non-rigorously that $EA_n \to \zeta(2) = \pi^2/6$. Aldous (1992) identified the limit in terms of a matching problem on a limit infinite tree. In this talk we construct the optimal matching on the infinite tree. This yields a rigorous proof of the $\zeta(2)$ limit and of the conjectured limit distribution of edge-costs and their rank-orders in the optimal matching. It also yields the asymptotic essential uniqueness (replica symmetry) property: every almost-optimal matching coincides with the optimal matching except on a small proportion of edges.
 

Eli Ben-Naim, Los Alamos National Laboratory

Extremal properties of random trees

We investigate extremal statistical properties such as the maximal and the minimal heights of randomly generated binary trees. By analyzing the master evolution equations we show that the cumulative distribution of extremal heights approaches a traveling wave form. The wave front in the minimal case is governed by the small-extremal-height tail of the distribution, and conversely, the front in the maximal case is governed by the large-extremal-height tail of the distribution. We determine several statistical characteristics of the extremal height distribution analytically. In particular, the expected minimal and maximal heights grow logarithmically with the tree size, N, h_min ~ v_min ln N, and h_max ~ v_max ln N, with v_min = 0.373365... and v_max = 4.31107..., respectively. Corrections to this asymptotic behavior are of order O(ln ln N).
 

Stefan Boettcher, Emory University

Efficient local search near phase transitions in combinatorial optimization

I will introduce Extremal Optimization, a new heuristic for finding high-quality solutions to hard optimization problems. For many physical and combinatorial optimization studied, Extremal Optimization appears to be particularly successful near phase transitions. I will present numerical results for the cost function and the backbone near phase transitions in combinatorial optimization problems for the case of random graph coloring and partitioning.
 

Christian Borgs, Microsoft Research

Phase transitions and slow mixing for H-coloring models

An H coloring of a graph G is a map from G to H that maps each edge in G into an edge in H. In applications to statistical physics, G is the underlying lattice, while H is the graph describing the constraints in a generalized hard core system.

In this talk, I consider random H-colorings of rectangular subsets of the hypercubic lattice, with a sperate weight factor (fugacity) for each color. It is shown that these fugacities can be chosen in such a way that the model exhibits a phase transition -- with multiple Gibbs states, and slow mixing for many natural algorithms. Namely, we show that any algorithm that is quasi-local in the sense that it changes at most a fraction rho < 1 of all sites has a mixing time which is exponential in the cross-section of the underlying rectangular box.

This work is joint work with Jennifer Chayes, Martin Dyer, and Prasad Tetali.
 

Mikio Braun, Universität Bonn

The noisy traveling salesman problem: robustness by randomization

We study noisy combinatorial optimization problems, i.e., combinatorial optimization problems, where the parameters defining the problem are random variables. The behavior of typical solutions with respect to the empirical Gibbs measure of one sampled instance (training instance) on a second sampled instance (test instance) is investigated. We argue that noisy optimization problems are highly relevant because most of the problems occurring in reality are intrinsically stochastic. We have chosen the traveling salesman problem to study the notion of robust optimization but the phenomena are expected to occur in a large number of continuous and combinatorial real world optimization problems.

We study a constructed example of the traveling salesman problem, where the following effect occurs: solutions drawn w.r.t. the Gibbs measure at finite temperature behave considerably better on the test instance, i.e., are more robust, than solutions at near zero temperature. This effect is known as overfitting in learning theory. Roughly speaking, the typical solutions for different sampled instances start to look too different below a certain temperature, and their performance on the test instance decreases. This might be linked to phenomena similar to parameter bifurcation.

In order to derive theoretical results, Gibbs sampling at finite temperature is interpreted as coarse-graining the set of all solutions. We provide large deviation bounds from statistical learning theory which yield a bound on the optimal coarsening scale.

Statistical mechanics approaches lead to alternative randomized algorithms for constructing robust solutions. Furthermore, we conjecture that there is a connection between the robustness of a solution sampled from the Gibbs distribution at finite temperature and the hardness of approximating the problem to the same relative error as the typical instance.
 

Jennifer Chayes, Microsoft Research

A phase transition in the optimum partitioning problem

The optimum partitioning problem is a canonical NP-complete problem of combinatorial optimization. We prove that the random version of this problem has a phase transition and establish the behavior of the model near the transition. In particular, we show that the phase transition is discontinuous or ``first-order,'' in contrast to the phase transitions established in other combinatorial models such as the random graph and the 2-satisfiability problem. We also discuss recent suggestions that the order of the phase transition may be related to the hardness of the problem.

The subject of the talk represents joint work with C. Borgs and B. Pittel.
 

Joe Culberson, University of Alberta

Frozen development at the phase transition

We can view the phase transitions of many NP-complete problems in the framework of a randomized construction which starts with a set of elements and then adds elementary substructures or parts one at a time in random order. In SAT we have boolean variables and add clauses, for graph problems we start with vertices and add edges, for CSP's we start with variables and add constraints. A part is frozen for a structure if adding the part would create an object that does not have the property defined by the NP-complete problem. This notion of frozen parts is closely related to the backbones and other frozen properties used in the analysis of phase transitions.

Using such a construction we consider empirical results on the rate at which edges become frozen for graph coloring. This shows strong evidence of an asymptotic discontinuity of the type that is associated with hard instances at the threshold. We can then relax the problem to ask what happens if we allow one or two edges to be improperly colored. Will this significantly affect the sudden jump in the number of frozen edges?

Alternatively, we can consider the complexity of solving problems with no frozen parts. For some NP-complete problems the unfrozen questions remain NP-complete, while for others they are in P. So far, we are not clear what is the correlation of these results with the existence of a discontinuity in frozen parts and with hard instances at the threshold.
 

Hervé Daudé, Université de Provence

k-XORSAT and sparse random matrices

Using ``exclusive or'' instead of ``usual or'' in the k-SAT problem leads to the k-XORSAT problem. In this talk we will first explain how the study of the phase transition of k-XORSAT can be related to the behavior of the number of vectors in the kernel of random sparse matrices over GF(2). Then some results on random sparse matrices over GF(2) will be presented in order to derive first bounds for the location of the transition of k-XORSAT.

This is joint work with Nadia Creignou and Olivier Dubois.
 

Demetrios Demopoulos, Rice University

Random 3-SAT: thickening the plot

In our work we present an experimental investigation of the dependency of average-case computational complexity of random 3-SAT on the density (ratio of number of clauses to variables), understood as a function of the order (number of variables) for fixed density. The questions we ask are: Is there a phase transition in which the complexity shifts from polynomial to exponential? Is the transition dependent or independent of the solver? Our data, mean and median running times, come from solving a large collection of random 3-SAT problems while systematically varying both densities and the order of the instances. We use three different complete SAT solvers, embodying very different underlying algorithms: GRASP, CPLEX and CUDD. We observe new phase transitions for all three solvers, where the median running time shifts from polynomial in the order to exponential. The location of the phase transition appears to be solver-dependent. Further experimentation, varying the BDD construction strategy for CUDD, shows that not only the shape of the median running times changes with the strategy, but the several phase transitions contained in the density-order surface (including the point of the hardest average computational complexity) are strategy-dependent. We believe these experimental observations are important for understanding the computational complexity of random 3-SAT, and can be used as a justification for developing density-aware solvers for 3-SAT.
 

Phillip Duxbury, Michigan State University

Phase transitions by constraint counting: rigidity percolation, matching and vertex cover

Two phase transitions will be discussed: Firstly the rigidity percolation transition which occurs as central force constraints are added to a floppy graph. Secondly the behavior of the minimum vertex cover as a function of the number of edges in a graph. These two problems are related to each other as the minimum vertex cover on a bipartite graph, is related to maximum cardinality bipartite matching, and so is rigidity percolation. The physics, phase transitions and algorithmic aspects of rigidity percolation and minimum vertex cover will be compared.
 

Tad Hogg, HP Labs

Exploiting combinatorial search structure with quantum computers

Quantum computers, if they can be built with enough qubits, can factor integers in polynomial time, a problem apparently intractable for conventional machines. However, such machines are unlikely to efficiently solve all combinatorial search problems in spite of their ability to rapidly evaluate exponentially many search states. Instead, they may be useful for ``typical'' searches arising in practice by operating on the entire search space at once, in contrast to conventional searches that only examine a small, far from random subset of the space.

Realizing this possibility requires matching the quantum algorithm to the structure of the problem's search space. While the detailed structure of a given instance is not known a priori, many recent studies of random problem ensembles have identified regularities related to phase transitions in behavior. This presentation will describe how these regularities apply to quantum search algorithms, and a range of open questions. In particular, real-world problems may differ from typical members of random ensembles, requiring a better understanding of problem structure to improve heuristic search, both quantum and conventional.
 

Russell Impagliazzo, University of California, San Diego

Hill-climbing is as good as Metropolis for planted bisection problems

A landmark paper of Jerrum and Sorkin proves that the Metropolis algorithm succeeds with high probability for random instances of the graph bisection problem drawn from the ``planted bisection'' model $G_{n,p,q}$. In this model, a graph is constructed from two initially disjoint random graphs, drawn from $G_{n,p}$, by adding edges between cross graph vertex pairs with some lower probability $q < p$. If $p-q = \omega(\sqrt{log n}\sqrt{m n}/n^2)$, then with high probability the bisection separating the two is the unique only optimal solution. They proved their result for $p-q =n^{-1/6+ \epsilon}$, significantly greater than needed for optimality. This is one of the few optimization problems for which Metropolis or simulated annealing are provably good. However, they left open the question of whether the full Metropolis algorithm was necessary, or whether degenerate cases of the algorithm such as random hill-climbing would also succeed.

Here, the behavior of simple randomized hill-climbing algorithms is examined for this model. We give a simple, polynomial-time, hill-climbing algorithm for this problem and show that it succeeds in finding the planted bisection with high probability if $p-q = \Omega(log^3 n^{-1/2})$, within polylog factors of the threshold. Furthermore, a universal randomized hill-climbing algorithm succeeds in finding the planted bisection in polynomial time if $p-q = \Omega( n^{-1/4 + \epsilon} \sqrt{m n}), for any $\epsilon > 0$. This universal algorithm is a degenerate case of both Metropolis and go-with-the-winners, so this result implies, extends, and unifies those by Jerrum and Sorkin, Dimitriou and Impagliazzo, and Juels.

Thus, there are no examples where these sophisticated heuristic methods have been proven to work, but where simple hill-climbing algorithms fail. This result emphasises the need to find instance distributions for optimization problems that can be used to discriminate between local search heuristic techniques.
 

Henry Kautz, University of Washington

Balance and filtering in structured satisfiable problems

New methods to generate hard random problem instances have driven progress on algorithms for deduction and constraint satisfaction. Last year we introduced a generator based on Latin squares that creates only satisfiable problems, and so can be used to accurately test incomplete (one sided) solvers. Hard instances in this model are associated with a threshold in the size of the backbone of the problem instances.

In our latest work we show that this generator creates instances that are empirically easier than those found by filtering the output of a mixed sat/unsat generator. Harder instances in both models may be created by imposing a balance condition. More generally, we show that the sat-only generator is one member of a family of related models that generate distributions ranging from ones that are everywhere tractable to ones that exhibit a sharp hardness threshold. We also discuss the critical role of the problem encoding in the performance of both systematic and local search solvers.

This is joint work with Dimitris Achlioptas, Carla Gomes, Yongshao Ruan, and Bart Selman.
 

Lefteris Kirousis, University of Patras

Upper bounds to the satisfiability threshold: a review of the rigorous results

In a series of papers, several groups of researchers have provided rigorous proofs for increasingly better upper bounds to the satisfiability threshold. Common basis of these proofs is the simple and well known first moment method (or variations of it), which is a direct application of the classical Markov inequality. However, the refinements of the first moment method used in the proofs depend on probabilistic techniques that provide and use new results for problems related to throwing balls into bins, coupon collecting, q-binomial coefficients, etc. We will present an outline of the main ideas of these techniques (the talk will appear as a review article jointly with A. Kaporis, Y. Stamatiou and M. Zito).
 

Jack Lutz, Iowa State University

The fractal geometry of complexity classes

The recent development of constructive and complexity-theoretic extensions of classical Hausdorff dimension has opened the way for applying techniques from fractal geometry to problems in computational complexity. In the past year and a half, various investigators have used this approach to shed new light on Boolean circuit-size complexity, approximability of MAX3SAT, polynomial-time reductions and completeness, randomness, efficient prediction, and data compression. More significantly, new relationships among computational complexity, Shannon entropy, and Kolmogorov complexity have been discovered. This talk will survey these developments and the prospects for further synthesis of complexity and information.
 

Madhav Marathe, Los Alamos National Laboratory

Succinctly specified problems: towards a predictive complexity theory

Several practical problems in VLSI, transportation science and high performance computing deal with highly regular instances represented in a compact fashion. I will discuss two commonly studied succinct specifications for representing such objects: hierarchical specifications and periodic specifications.

In this talk I will describe our research aimed at developing a ``predictive complexity theory''. The goal is to characterize simultaneously the complexity and approximability of a large class of combinatorial problems when instances are specified using such succinct specifications. Three basic elements fit together naturally and simply to form the basis of such a theory: (i) strongly-local (graph/hypergraph) replacements/reductions, (ii) relational/algebraic representability, and (iii) generalized relational/algebraic satisfiability problems.

Two important applications of the results include:

(A) Development of efficient approximation algorithms and approximation schemes with provable performance guarantees for large classes of natural PSPACE-, NEXPTIME-hard optimization problems, and proof of the non-efficient approximability of others.

(B) Possible implications for Freedman's recently proposed ideas for attacking the P vs NP problem.

This is joint work with Professors Harry B. Hunt III, Daniel J. Rosenkrantz and Richard E. Stearns (University at Albany-SUNY).
 

Stephan Mertens, Universität Magdeburg

Random costs in combinatorial optimization

The random cost problem is the problem of identifying the minimum in a list of random numbers. By definition, this problem cannot be solved faster than by exhaustive search. It is shown that a classical NP-hard optimization problem, number partitioning, is essentially equivalent to the random cost problem. On the one hand this explains the bad performance of heuristic approaches to the number partitioning problem, but on the other hand it allows one to calculate the probability distributions of the optimum and sub-optimum costs.
 

Michael Molloy, University of Toronto

Models for random constraint satisfaction problems

We introduce a class of models for random Constraint Satisfaction Problems. This class includes and generalizes many previously studied models. We characterize those models from our class which are asymptotically interesting in the sense that the limiting probability of satisfiability changes significantly as the number of constraints increases. We also discuss models which exhibit a sharp threshold for satisfiability in the sense that the limiting probability jumps from 0 to 1 suddenly as the number of constraints increases.
 

Cris Moore, University of New Mexico / Santa Fe Institute

Almost all graphs with degree 4.03 or less (including 4-regular graphs) are 3-colorable

Achlioptas and Molloy used the method of differential equations to analyze a greedy list-coloring heuristic on random graphs, showing that the 3-colorability transition is at or above 3.847. We improve this lower bound to 4.03 by analyzing a heuristic which prefers to color high-degree nodes first. The same method can be used to show that almost all 4-regular graphs are 3-colorable.

This is joint work with Dimitris Achlioptas.
 

Andrew Parkes, University of Oregon

Phase transitions, constraint relaxation, and distributed search

Real problems are often over-constrained. Phase transition methods can say an instance is almost certainly unsatisfiable, however, it would be useful if they could also give guidance as to which constraints should be relaxed to have a solution. Degeneracy observed in the maximum satisfiability of random 3-SAT suggests that many equivalent-cost relaxations are available. Also, in systems with multiple order parameters there is freedom as to which way to move onto the satisfiable side of the phase transition surface. Good choices of relaxation should help the search algorithm with minimal reduction of final solution quality. We give results of preliminary investigations on such interactions of phase transitions, constraint relaxation and distributed/parallel search methods.
 

Christian Reidys, Los Alamos National Laboratory

Combinatorial landscapes

Fitness landscapes have proven to be a valuable concept in evolutionary biology, combinatorial optimization, and the physics of disordered systems. A fitness landscape is a mapping from a configuration space into the real numbers. The configuration space is equipped with some notion of adjacency, nearness, distance or accessibility. Landscape theory has emerged as an attempt to devise suitable mathematical structures for describing the ``static'' properties of landscapes as well as their influence on the dynamics of adaptation. In this talk we focus on the connections of landscape theory with algebraic combinatorics and random graph theory, where exact results are available.

This talk will be organized as follows: We first identify the structure of configuration spaces either as undirected, unweighted graphs or as reversible Markov chains. This sets the stage for decomposition of landscapes in terms of particular orthonormal bases that take into account the structure of the underlying configuration space. This ``spectral'' approach concentrates on ruggedness, neutrality and isotropy and is of particular relevance for combinatorial optimization problems and disordered systems. Landscapes arising in biology are based upon an underlying genotype-phenotype map which determines key features of the landscape. We discuss two paradigmatic examples of genotype phenotype maps: RNA secondary structure folding and sequential dynamical systems. The analysis of these examples naturally leads to a random graph theory of neutrality. We finally review dynamical aspects in landscape theory, in particular the quasispecies model.
 

Bart Selman, Cornell University

Heavy-tailed phenomena in combinatorial search

Recently, it has been found that the cost distributions of randomized backtrack search in combinatorial domains are often heavy-tailed. Such heavy-tailed distributions explain the high variability observed when using backtrack-style procedures. A good understanding of this phenomenon can lead to better search techniques. For example, restart strategies provide a good mechanism for eliminating the heavy-tailed behavior and boosting the overall search performance. Several state-of-the-art SAT solvers now incorporate such restart mechanisms. The study of heavy-tailed phenomena in combinatorial search has so far been been largely based on empirical data. We introduce several abstract tree search models, and show formally how heavy-tailed cost distribution can arise in backtrack search. We also discuss how these insights may facilitate the development of better combinatorial search methods.

This is joint work with Carla Gomes and Hubie Chen.
 

Alistair Sinclair, University of California, Berkeley

Sampling dimer configurations in arbitrary bipartite graphs

I will present a Markov chain Monte Carlo algorithm that samples dimer configurations (perfect matchings) in an arbitrary bipartite graph from the Gibbs distribution with arbitrary non-negative weights on the edges. The algorithm provably requires only a polynomial number of steps per sample. As a corollary, one obtains a polynomial-time algorithm that computes the partition function of an arbitrary bipartite dimer system to any desired accuracy. Previously, such algorithms had been known only for restricted classes of (bipartite) graphs such as dense graphs and lattices.

This is joint work with Mark Jerrum and Eric Vigoda.
 

Zoltan Toroczkai, Los Alamos National Laboratory

Solution of the scalability problem and algorithmic improvement for the massively parallel algorithm, using methods from statistical mechanics

Based on methods related to the statistical mechanics of growing non-equilibrium interfaces, we develop a technique that can be used to show the asymptotic scalability of conservative massively parallel algorithms (CMPA-s) for discrete event simulations, i.e., the fact that the efficiency of such computational schemes does not vanish with increasing number of processing elements. CMPA-s are extremely robust parallel schemes that are used to simulate a large class of systems with inherently asynchronous dynamics, such as magnetization dynamics of extended spin systems, cellphone networks, agent-based systems, epidemics spreading, etc. Our method can be extended to help engineer algorithmically improved efficient parallel schemes, one example of which is presented.

This is joint work with G. Korniss.
 

Wim van Dam, University of California, Berkeley

Limits on adiabatic quantum computing

Recently, Farhi et al. described a novel minimization algorithm that relies on the quantum adiabatic theorem in quantum mechanics. It was suggested that with this approach NP-complete problems would maybe allow a probabilistic, polynomial time solution. Here we discuss the strengths and weaknesses of the adiabatic paradigm. More specifically we show that the minimization procedure can easily be ``fooled'' by a local minimum. This result indicates that, in general, quantum adiabatic computing will not be able to solve NP-complete problems in poly-time.

This is joint work with Mike Mosca and Umesh Vazirani.
 

Joseph Yukich, Lehigh University

Limit theory for random sequential packing and deposition

Consider sequential packing of unit balls in a large cube, as in the Rényi car-parking model, but in any dimension and with finite input. We prove a law of large numbers and central limit theorem for the number of packed balls in the thermodynamic limit. We prove analogous results for numerous related applied models, including cooperative sequential adsorption, ballistic deposition, and spatial birth-growth models.

The proofs are based on a general law of large numbers and central limit theorem for ``stabilizing'' functionals of marked point processes of independent uniform points in a large cube, which are of independent interest. ``Stabilization'' means, loosely, that local modifications have only local effects.