Dimitris Achlioptas

NeurIPS Conference 2020 Conference Paper

Bad Global Minima Exist and SGD Can Reach Them

• Shengchao Liu
• Dimitris Papailiopoulos
• Dimitris Achlioptas

Several works have aimed to explain why overparameterized neural networks generalize well when trained by Stochastic Gradient Descent (SGD). The consensus explanation that has emerged credits the randomized nature of SGD for the bias of the training process towards low-complexity models and, thus, for implicit regularization. We take a careful look at this explanation in the context of image classification with common deep neural network architectures. We find that if we do not regularize \emph{explicitly}, then SGD can be easily made to converge to poorly-generalizing, high-complexity models: all it takes is to first train on a random labeling on the data, before switching to properly training with the correct labels. In contrast, we find that in the presence of explicit regularization, pretraining with random labels has no detrimental effect on SGD. We believe that our results give evidence that explicit regularization plays a far more important role in the success of overparameterized neural networks than what has been understood until now. Specifically, in suppressing complicated models that got lucky with the training data, regularization not only makes simple models that fit the data well the global optima, but it also clears the way to make them discoverable by local methods, such as SGD.

FOCS Conference 2019 Conference Paper

Beyond the Lovász Local Lemma: Point to Set Correlations and Their Algorithmic Applications

• Dimitris Achlioptas
• Fotis Iliopoulos
• Alistair Sinclair

Following the groundbreaking algorithm of Moser and Tardos for the Lovasz Local Lemma (LLL), there has been a plethora of results analyzing local search algorithms for various constraint satisfaction problems. The algorithms considered fall into two broad categories: resampling algorithms, analyzed via different algorithmic LLL conditions; and backtracking algorithms, analyzed via entropy compression arguments. This paper introduces a new convergence condition that seamlessly handles resampling, backtracking, and hybrid algorithms, i. e. , algorithms that perform both resampling and backtracking steps. Unlike previous work on the LLL, our condition replaces the notion of a dependency or causality graph by quantifying point-to-set correlations between bad events. As a result, our condition simultaneously: (i) captures the most general algorithmic LLL condition known as a special case; (ii) significantly simplifies the analysis of entropy compression applications; (iii) relates backtracking algorithms, which are conceptually very different from resampling algorithms, to the LLL; and most importantly (iv) allows for the analysis of hybrid algorithms, which were outside the scope of previous techniques. We give several applications of our condition, including a new hybrid vertex coloring algorithm that extends the recent breakthrough result of Molloy for coloring triangle-free graphs to arbitrary graphs.

SAT Conference 2018 Conference Paper

Fast and Flexible Probabilistic Model Counting

• Dimitris Achlioptas
• Zayd S. Hammoudeh
• Panos Theodoropoulos

Abstract We present a probabilistic model counter that can trade off running time with approximation accuracy. As in several previous works, the number of models of a formula is estimated by adding random parity constraints (equations). One key difference with prior works is that the systems of parity equations used correspond to the parity check matrices of Low Density Parity Check (LDPC) error-correcting codes. As a result, the equations tend to be much shorter, often containing fewer than 10 variables each, making the search for models that also satisfy the parity constraints far more tractable. The price paid for computational tractability is that the statistical properties of the basic estimator are not as good as when longer constraints are used. We show how one can deal with this issue and derive rigorous approximation guarantees by performing more solver invocations.

SAT Conference 2018 Conference Paper

Fast Sampling of Perfectly Uniform Satisfying Assignments

• Dimitris Achlioptas
• Zayd S. Hammoudeh
• Panos Theodoropoulos

Abstract We present an algorithm for perfectly uniform sampling of satisfying assignments, based on the exact model counter sharpSAT and reservoir sampling. In experiments across several hundred formulas, our sampler is faster than the state of the art by 10 to over 100, 000 times.

I&C Journal 2018 Journal Article

Symmetric graph properties have independent edges

• Dimitris Achlioptas
• Paris Siminelakis

In the study of random structures we often face a trade-off between realism and tractability, the latter typically enabled by independence assumptions. In this work we initiate an effort to bridge this gap by developing tools that allow us to work with independence without assuming it. Let G n be the set of all graphs on n vertices and let S be an arbitrary subset of G n, e. g. , the set of all graphs with m edges. The study of random networks can be seen as the study of properties that are true for most elements of S, i. e. , that are true with high probability for a uniformly random element of S. With this in mind, we pursue the following question: What are general sufficient conditions for the uniform measure on a set of graphs S ⊆ G n to be well-approximable by a product measure on the set of all possible edges?

SAT Conference 2017 Conference Paper

Probabilistic Model Counting with Short XORs

• Dimitris Achlioptas
• Panos Theodoropoulos

Abstract The idea of counting the number of satisfying truth assignments (models) of a formula by adding random parity constraints can be traced back to the seminal work of Valiant and Vazirani, showing that NP is as easy as detecting unique solutions. While theoretically sound, the random parity constraints in that construction have the following drawback: each constraint, on average, involves half of all variables. As a result, the branching factor associated with searching for models that also satisfy the parity constraints quickly gets out of hand. In this work we prove that one can work with much shorter parity constraints and still get rigorous mathematical guarantees, especially when the number of models is large so that many constraints need to be added. Our work is based on the realization that the essential feature for random systems of parity constraints to be useful in probabilistic model counting is that the geometry of their set of solutions resembles an error-correcting code.

SODA Conference 2016 Conference Paper

Bounds for Random Constraint Satisfaction Problems via Spatial Coupling

• Dimitris Achlioptas
• Seyed Hamed Hassani
• Nicolas Macris
• Rüdiger L. Urbanke

SODA Conference 2016 Conference Paper

Focused Stochastic Local Search and the Lovász Local Lemma

• Dimitris Achlioptas
• Fotis Iliopoulos

We develop tools for analyzing focused stochastic local search algorithms. These are algorithms that search a state space probabilistically by repeatedly selecting a constraint that is violated in the current state and moving to a random nearby state which, hopefully, addresses the violation without introducing many new ones. A large class of such algorithms arise from algorithmizations of the Lovász Local Lemma, a non-constructive tool for proving the existence of satisfying states. Here we give tools that provide a unified analysis of such algorithms and of many more, expressing them as instances of a general framework.

UAI Conference 2015 Conference Paper

Stochastic Integration via Error-Correcting Codes

• Dimitris Achlioptas
• Pei Jiang 0001

We consider the task of summing a non-negative function f over a discrete set Ω, e. g. , to compute the partition function of a graphical model. Ermon et al. have shown that in a probabilistic approximate sense summation can be reduced to maximizing f over random subsets of Ω defined by parity (XOR) constraints. Unfortunately, XORs with many variables are computationally intractable, while XORs with few variables have poor statistical performance. We introduce two ideas to address this problem, both motivated by the theory of error-correcting codes. The first is to maximize f over explicitly generated random affine subspaces of Ω, which is equivalent to unconstrained maximization of f over an exponentially smaller domain. The second idea, closer in spirit to the original approach, is to use systems of linear equations defining Low Density Parity Check (LDPC) error-correcting codes. Even though the equations in such systems only contain O(1) variables each, their sets of solutions (codewords) have excellent statistical properties. By combining these ideas we achieve dramatic speedup over the original approach and levels of accuracy that were completely unattainable.

FOCS Conference 2014 Conference Paper

Random Walks That Find Perfect Objects and the Lovasz Local Lemma

• Dimitris Achlioptas
• Fotis Iliopoulos

We give an algorithmic local lemma by establishing a sufficient condition for the uniform random walk on a directed graph to reach a sink quickly. Our work is inspired by Moser's entropic method proof of the Lovasz Local Lemma (LLL) for satisfiability and completely bypasses the Probabilistic Method formulation of the LLL. In particular, our method works when the underlying state space is entirely unstructured. Similarly to Moser's argument, the key point is that algorithmic progress is measured in terms of entropy rather than energy (number of violated constraints) so that termination can be established even under the proliferation of states in which every step of the algorithm (random walk) increases the total number of violated constraints.

NeurIPS Conference 2013 Conference Paper

Near-Optimal Entrywise Sampling for Data Matrices

• Dimitris Achlioptas
• Zohar Karnin
• Edo Liberty

We consider the problem of independently sampling $s$ non-zero entries of a matrix $A$ in order to produce a sparse sketch of it, $B$, that minimizes $\|A-B\|_2$. For large $m \times n$ matrices, such that $n \gg m$ (for example, representing $n$ observations over $m$ attributes) we give distributions exhibiting four important properties. First, they have closed forms for the probability of sampling each item which are computable from minimal information regarding $A$. Second, they allow sketching of matrices whose non-zeros are presented to the algorithm in arbitrary order as a stream, with $O(1)$ computation per non-zero. Third, the resulting sketch matrices are not only sparse, but their non-zero entries are highly compressible. Lastly, and most importantly, under mild assumptions, our distributions are provably competitive with the optimal offline distribution. Note that the probabilities in the optimal offline distribution may be complex functions of all the entries in the matrix. Therefore, regardless of computational complexity, the optimal distribution might be impossible to compute in the streaming model.

SAT Conference 2012 Conference Paper

Exponential Lower Bounds for DPLL Algorithms on Satisfiable Random 3-CNF Formulas

• Dimitris Achlioptas
• Ricardo Menchaca-Méndez

Abstract We consider the performance of a number of DPLL algorithms on random 3-CNF formulas with n variables and m = rn clauses. A long series of papers analyzing so-called “myopic” DPLL algorithms has provided a sequence of lower bounds for their satisfiability threshold. Indeed, for each myopic algorithm \({\mathcal A}\) it is known that there exists an algorithm-specific clause-density, \(r_{\mathcal A}\), such that if \(r < r_{\mathcal A}\), the algorithm finds a satisfying assignment in linear time. For example, \(r_{\mathcal A}\) equals 8/3 = 2. 66. . for orderred-dll and 3. 003. .. for generalized unit clause. We prove that for densities well within the provably satisfiable regime, every backtracking extension of either of these algorithms takes exponential time. Specifically, all extensions of orderred-dll take exponential time for r > 2. 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_{\mathcal A}\).

FOCS Conference 2008 Conference Paper

Algorithmic Barriers from Phase Transitions

• Dimitris Achlioptas
• Amin Coja-Oghlan

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 many of these problems, all known polynomial-time algorithms stop finding solutions at much smaller densities. For example, it is well-known that it is easy to color a random graph using twice as many colors as its chromatic number. Indeed, some of the simplest possible coloring algorithms achieve this goal. Given the simplicity of those algorithms, one would expect room for improvement. Yet, to date, no algorithm is known that uses (2 - epsiv)chi colors, in spite of efforts by numerous researchers over the years. In view of the remarkable resilience of this factor of 2 against every algorithm hurled at it, we find it natural to inquire into its origin. We do so by analyzing the evolution of the set of k-colorings of a random graph, viewed as a subset of {1, .. ., k} n, as edges are added. We prove that the factor of 2 corresponds in a precise mathematical sense to a phase transition in the geometry of this set. Roughly speaking, we prove that the set of k-colorings looks like a giant ball for k ges 2chi, but like an error-correcting code for k les (2 - epsiv)chi. We also prove that an analogous phase transition occurs both in random k-SAT and in random hypergraph 2-coloring. And that for each of these three problems, the location of the transition corresponds to the point where all known polynomial-time algorithms fail. To prove our results we develop a general technique that allows us to establish rigorously much of the celebrated 1-step replica-symmetry-breaking hypothesis of statistical physics for random CSPs.

STOC Conference 2006 Conference Paper

On the solution-space geometry of random constraint satisfaction problems

• Dimitris Achlioptas
• Federico Ricci-Tersenghi

For 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.

STOC Conference 2005 Conference Paper

On the bias of traceroute sampling: or, power-law degree distributions in regular graphs

• Dimitris Achlioptas
• Aaron Clauset
• David Kempe 0001
• Cristopher Moore

Understanding the structure of the Internet graph is a crucial step for building accurate network models and designing efficient algorithms for Internet applications. Yet, obtaining its graph structure is a surprisingly difficult task, as edges cannot be explicitly queried. Instead, empirical studies rely on traceroutes to build what are essentially single-source, all-destinations, shortest-path trees. These trees only sample a fraction of the network's edges, and a recent paper by Lakhina et al. found empirically that the resuting sample is intrinsically biased. For instance, the observed degree distribution under traceroute sampling exhibits a power law even when the underlying degree distribution is Poisson.In this paper, we study the bias of traceroute sampling systematically, and, for a very general class of underlying degree distributions, calculate the likely observed distributions explicitly. To do this, we use a continuous-time realization of the process of exposing the BFS tree of a random graph with a given degree distribution, calculate the expected degree distribution of the tree, and show that it is sharply concentrated. As example applications of our machinery, we show how traceroute sampling finds power-law degree distributions in both δ-regular and Poisson-distributed random graphs. Thus, our work puts the observations of Lakhina et al. on a rigorous footing, and extends them to nearly arbitrary degree distributions.

SODA Conference 2004 Conference Paper

Exponential bounds for DPLL below the satisfiability threshold

• Dimitris Achlioptas
• Paul Beame
• Michael Molloy 0001

AAAI Conference 2004 Conference Paper

Hiding Satisfying Assignments: Two Are Better than One

• Dimitris Achlioptas

The evaluation of incomplete satisfiability solvers depends critically on the availability of hard satisfiable instances. A plausible source of such instances are k-CNF formulas whose clauses are chosen uniformly at random among all clauses satisfying some randomly chosen truth assignment A. Unfortunately, instances generated in this manner are relatively easy and can be solved efficiently by practical heuristics. Roughly speaking, as the number of clauses is increased, A acts as a stronger and stronger attractor. Motivated by recent results on the geometry of the space of solutions for random k-SAT and NAE-k-SAT instances, we propose a very simple twist on this model that greatly increases the hardness of the resulting formulas. Namely, in addition to forbidding the clauses violated by the hidden assignment A, we also forbid the clauses violated by its complement, so that both A and A are satisfying. It appears that under this “symmetrization” the effects of the two attractors largely cancel out, making it much harder for an algorithm to “feel” (and find) either one. We give theoretical and experimental evidence supporting this assertion.

STOC Conference 2004 Conference Paper

The two possible values of the chromatic number of a random graph

• Dimitris Achlioptas
• Assaf Naor

For every d > 0, let k d be the smallest integer k such that d < 2k log k. We prove that the chromatic number of a random graph G(n,d/n) is either k d or k d+1 almost surely. If d ∈ (2k log k - log k, 2k log k) we further prove that the chromatic number almost surely equals k+1.

FOCS Conference 2003 Conference Paper

On the Maximum Satisfiability of Random Formulas

• Dimitris Achlioptas
• Assaf Naor
• Yuval Peres

Maximum satisfiability is a canonical NP-complete problem that appears empirically hard for random instances. At the same time, it is rapidly becoming a canonical problem for statistical physics. In both of these realms, evaluating new ideas relies crucially on knowing the maximum number of clauses one can typically satisfy in a random k-CNF formula. In this paper we give asymptotically tight estimates for this quantity. Our result gives very tight bounds for the fraction of satisfiable clauses in a random k-CNF. In particular, for k > 2 it improves upon all previously known such bound.

STOC Conference 2003 Conference Paper

The threshold for random k-SAT is 2 k (ln 2 - O(k))

• Dimitris Achlioptas
• Yuval Peres

Let F k (n,m) be a random k -SAT formula on n variables formed by selecting uniformly and independently m out of all possible k -clauses. It is well-known that for r ≥ 2 k ln 2 , F k (n,rn) is unsatisfiable with probability 1-o(1) . We prove that there exists a sequence t k = O(k) such that for r ≥ 2 k ln 2 - t k , F k (n,rn) is satisfiable with probability 1-o(1) .Our technique yields an explicit lower bound for every k which for k > 3 improves upon all previously known bounds. For example, when k=10 our lower bound is 704.94 while the upper bound is 708.94.

STOC Conference 2002 Conference Paper

Almost all graphs with average degree 4 are 3-colorable

• Dimitris Achlioptas
• Cristopher Moore

The technique of using differential equations to approximate the mean path of Markov chains has proved very useful in the average-case analysis of algorithms. Here, we significantly expand the range of this technique, by showing that it can be used to handle algorithms that favor high-degree vertices. In particular, we consider the problem of 3-coloring sparse random graphs and analyze a "smoothed" version of the Brelaz heuristic. This allows us to prove that i) almost all graphs with average degree d , i.e. G ( n,p = d/n ), are 3-colorable for d ≤ 4.03, and that ii) almost all 4-regular graphs are 3-colorable. This improves over the previous lower bound of 3.847 for the G ( n,p ) 3-colorability threshold and gives the first non trivial result on the 3-colorability of random regular graphs.

FOCS Conference 2002 Conference Paper

The Asymptotic Order of the Random k -SAT Threshold

• Dimitris Achlioptas
• Cristopher Moore

Form a random k-SAT formula on n variables by selecting uniformly and independently m=rn clauses out of all 2/sup k/ (/sub k//sup n/) possible k-clauses. The satisfiability threshold conjecture asserts that for each k there exists a constant r/sub k/ such that, as n tends to infinity, the probability that the formula is satisfiable tends to 1 if r r/sub k/. It has long been known that 2/sup k//k 2/sup k-1/ ln 2-d/sub k/, where d/sub k//spl rarr/(1+ln2)/2. Our proof also allows a blurry glimpse of the "geometry" of the set of satisfying truth assignments.

STOC Conference 2001 Conference Paper

A sharp threshold in proof complexity

• Dimitris Achlioptas
• Paul Beame
• Michael Molloy 0001

We give the first example of a sharp threshold in proof complexity. More precisely, we show that for any sufficiently small ε>0 and Δ>2.28 , random formulas consisting of (1-ε)n 2-clauses and &Dgr n 3-clauses, which are known to be unsatisfiable almost certainly, almost certainly require resolution and Davis-Putnam proofs of unsatisfiability of exponential size, whereas it is easily seen that random formulas with (1+ε)n 2-clauses (and Δ n 3 clauses) have linear size proofs of unsatisfiability almost certainly. A consequence of our result also yields the first proof that typical random 3-CNF formulas at ratios below the generally accepted range of the satisfiability threshold (and thus expected to be satisfiable almost certainly) cause natural Davis-Putnam algorithms to take exponential time to find satisfying assignments.

STOC Conference 2001 Conference Paper

Fast computation of low rank matrix

• Dimitris Achlioptas
• Frank McSherry

Given a matrix A it is often desirable to find an approximation to A that has low rank. We introduce a simple technique for accelerating the computation of such approximations when A has strong spectral structure, i.e., when the singular values of interest are significantly greater than those of a random matrix with size and entries similar to A . Our technique amounts to independently sampling and/or quantizing the entries of A , thus speeding up computation by reducing the number of non-zero entries and/or the length of their representation. Our analysis is based on observing that the acts of sampling and quantization can be viewed as adding a random matrix E to A , whose entries are independent random variables with zero-mean and bounded variance. Since, with high probability, E has very weak spectral structure, we can prove that the effect of sampling and quantization nearly vanishes when a low rank approximation to A+E is computed. In fact, the stronger the spectral structure of A , the more of its entries we can afford to discard and, ultimately, the faster we can discover that structure. We give bounds on the quality of our approximation both in the L2 and in the Frobenius norm.

TCS Journal 2001 Journal Article

Lower bounds for random 3-SAT via differential equations

• Dimitris Achlioptas

It is widely believed that the probability of satisfiability for random k-SAT formulae exhibits a sharp threshold as a function of their clauses-to-variables ratio. For the most studied case, k=3, there have been a number of results during the last decade providing upper and lower bounds for the threshold's potential location. All lower bounds in this vein have been algorithmic, i. e. , in each case a particular algorithm was shown to satisfy random instances of 3-SAT with probability 1−o(1) if the clauses-to-variables ratio is below a certain value. We show how differential equations can serve as a generic tool for analyzing such algorithms by rederiving most of the known lower bounds for random 3-SAT in a simple, uniform manner.

TCS Journal 2001 Journal Article

Rigorous results for random (2+p)-SAT

• Dimitris Achlioptas
• Lefteris M. Kirousis
• Evangelos Kranakis
• Danny Krizanc

In recent years there has been significant interest in the study of random k-SAT formulae. For a given set of n Boolean variables, let Bk denote the set of all possible disjunctions of k distinct, non-complementary literals from its variables (k-clauses). A random k-SAT formula Fk(n, m) is formed by selecting uniformly and independently m clauses from Bk and taking their conjunction. Motivated by insights from statistical mechanics that suggest a possible relationship between the “order” of phase transitions and computational complexity, Monasson and Zecchina (Phys. Rev. E 56(2) (1997) 1357) proposed the random (2+p)-SAT model: for a given p∈[0, 1], a random (2+p)-SAT formula, F2+p(n, m), has m randomly chosen clauses over n variables, where pm clauses are chosen from B3 and (1−p)m from B2. Using the heuristic “replica method” of statistical mechanics, Monasson and Zecchina gave a number of non-rigorous predictions on the behavior of random (2+p)-SAT formulae. In this paper we give the first rigorous results for random (2+p)-SAT, including the following surprising fact: for p⩽2/5, with probability 1−o(1), a random (2+p)-SAT formula is satisfiable iff its 2-SAT subformula is satisfiable. That is, for p⩽2/5, random (2+p)-SAT behaves like random 2-SAT.

NeurIPS Conference 2001 Conference Paper

Sampling Techniques for Kernel Methods

• Dimitris Achlioptas
• Frank Mcsherry
• Bernhard Schölkopf

We propose randomized techniques for speeding up Kernel Principal Component Analysis on three levels: sampling and quantization of the Gram matrix in training, randomized rounding in evaluating the kernel expansions, and random projections in evaluating the kernel itself. In all three cases, we give sharp bounds on the accuracy of the obtained ap- proximations. Rather intriguingly, all three techniques can be viewed as instantiations of the following idea: replace the kernel function by a “randomized kernel” which behaves like

SODA Conference 2001 Conference Paper

The phase transition in 1-in-k SAT and NAE 3-SAT

• Dimitris Achlioptas
• Arthur D. Chtcherba
• Gabriel Istrate
• Cristopher Moore

FOCS Conference 2001 Conference Paper

Web Search via Hub Synthesis

• Dimitris Achlioptas
• Amos Fiat
• Anna R. Karlin
• Frank McSherry

We present a model for web search that captures in a unified manner three critical components of the problem: how the link structure of the web is generated, how the content of a web document is generated, and how a human searcher generates a query. The key to this unification lies in capturing the correlations between these components in terms of proximity in a shared latent semantic space. Given such a combined model, the correct answer to a search query is well defined, and thus it becomes possible to evaluate web search algorithms rigorously. We present a new web search algorithm, based on spectral techniques, and prove that it is guaranteed to produce an approximately correct answer in our model. The algorithm assumes no knowledge of the model, and is well-defined regardless of the model's accuracy.

TCS Journal 2000 Journal Article

Competitive analysis of randomized paging algorithms

• Dimitris Achlioptas
• Marek Chrobak
• John Noga

The paging problem is defined as follows: we are given a two-level memory system, in which one level is a fast memory, called cache, capable of holding k items, and the second level is an unbounded but slow memory. At each given time step, a request to an item is issued. Given a request to an item p, a miss occurs if p is not present in the fast memory. In response to a miss, we need to choose an item q in the cache and replace it by p. The choice of q needs to be made on-line, without the knowledge of future requests. The objective is to design a replacement strategy with a small number of misses. In this paper we use competitive analysis to study the performance of randomized on-line paging algorithms. Our goal is to show how the concept of work functions, used previously mostly for the analysis of deterministic algorithms, can also be applied, in a systematic fashion, to the randomized case. We present two results: we first show that the competitive ratio of the marking algorithm is exactly 2Hk−1. Previously, it was known to be between Hk and 2Hk. Then we provide a new, Hk -competitive algorithm for paging. Our algorithm, as well as its analysis, is simpler than the known algorithm by McGeoch and Sleator. Another advantage of our algorithm is that it can be implemented with complexity bounds independent of the number of past requests: O(k2 log k) memory and O(k2) time per request.

AAAI Conference 2000 Conference Paper

Generating Satisfiable Problem Instances

• Dimitris Achlioptas
• Cornell University; Henry Kautz

A major difficulty in evaluating incomplete local search style algorithms for constraint satisfaction problems is the need for a source of hard problem instances that are guaranteed to be satisfiable. A standard approach to evaluate incomplete search methods has been to use a general problem generator and a complete search method to filter out the unsatisfiable instances. Unfortunately, this approach cannot be used to create problem instances that are beyond the reach of complete search methods. So far, it has proven to be surprisingly difficult to develop a direct generator for satisfiable instances only. In this paper, we propose a generator that only outputs satisfiable problem instances. We also show how one can finely control the hardness of the satisfiable instances by establishing a connection between problem hardness and a new kind of phase transition phenomenon in the space of problem instances. Finally, we use our problem distribution to show the easy-hard-easy pattern in search complexity for local search procedures, analogous to the previously reported pattern for complete search methods.

FOCS Conference 2000 Conference Paper

Optimal myopic algorithms for random 3-SAT

• Dimitris Achlioptas
• Gregory B. Sorkin

Let F/sub 3/(n, m) be a random 3-SAT formula formed by selecting uniformly, independently and with replacement, m clauses among all 8(/sup n/C/sub 3/) possible 3-clauses over n variables. It has been conjectured that there exists a constant r/sub 3/ such that, for any /spl epsiv/>0, F/sub 3/[n, (r/sub 3/-/spl epsiv/)n] is almost surely satisfiable, but F/sub 3/[n, (r/sub 3/+/spl epsiv/)n] is almost surely unsatisfiable. The best lower bounds for the potential value of r/sub 3/ have come form analyzing rather simple extensions of unit-clause propagation. It was shown by D. Achlioptas (2000) that all these extensions can be cast in a common framework and analyzed in a uniform manner by employing differential equations. We determine optimal algorithms that are expressible in that framework, establishing r/sub 3/>3. 26. We extend the analysis via differential equations, and make extensive use of a new optimization problem that we call the "max-density multiple-choice knapsack" problem. The structure of optimal knapsack solutions elegantly characterizes the choices made by an optimal algorithm.

STOC Conference 2000 Conference Paper

Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)

• Dimitris Achlioptas

FOCS Conference 1997 Conference Paper

The Analysis of a List-Coloring Algorithm on a Random Graph

• Dimitris Achlioptas
• Michael Molloy 0001

We introduce a natural k-coloring algorithm and analyze its performance on random graphs with constant expected degree c (G/sub n, p=c/n/). For k=3 our results imply that almost all graphs with n vertices and 1. 923 n edges are 3-colorable. This improves the lower bound on the threshold for random 3-colorability significantly and settles the last case of a long-standing open question of Bollobas. We also provide a tight asymptotic analysis of the algorithm. We show that for all k/spl ges/3, if c/spl les/k In k-3/2k then the algorithm almost surely succeeds, while for any /spl epsiv/>0, and k sufficiently large, if c/spl ges/(1+/spl epsiv/)k In k then the algorithm almost surely fails. The analysis is based on the use of differential equations to approximate the mean path of certain Markov chains.