Given a collection of events in a probability space it is often desirable to bound from below the probability of arbitrary intersections of them, in the presence of negative correlation, i.e., when the occurrence of each event may make the occurrence of certain other events less likely. A classic tool for modelling negative correlation is a “dependency” graph, whose vertices correspond to events and whose edges indicate dependence. When the dependency graph is sufficiently sparse, the famous Lovász Local Lemma gives an explicit, strictly positive lower bound for the probability of every intersection. Here we extend the dependency graph setting from probabilities of intersections of events to arbitrary supermodular functions and derive corresponding explicit, strictly positive lower bounds.

The celebrated Four Functions Theorem of Ahlswede and Daykin is a functional correlation inequality on distributive lattices with myriad applications. Ruozzi proved a variant of the inequality and used it to settle a major conjecture in the area of graphical models. We prove a new functional correlation inequality in the same vein which simplifies the proof of both the Four Functions Theorem and of Ruozzi’s inequality and suggests a unified picture for correlation inequalities on distributive lattices.

The 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).

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.

We consider the task of designing Local Computation Algorithms (LCA) for applications of the Lovasz Local Lemma (LLL). LCA is a class of sublinear algorithms proposed by Rubinfeld et al. that have received a lot of attention in recent years. The LLL is an existential, sufficient condition for a collection of sets to have non-empty intersection (in applications, often, each set comprises all objects having a certain property). The ground-breaking algorithm of Moser and Tardos made the LLL fully constructive, following earlier results by Beck and Alon giving algorithms under significantly stronger LLL-like conditions. LCAs under those stronger conditions were given in Rubinfeld et al., where it was asked if the Moser-Tardos algorithm can be used to design LCAs under the standard LLL condition. The main contribution of this paper is to answer this question affirmatively. In fact, our techniques yield LCAs for settings beyond the standard LLL condition.

This issue of SICOMP contains 10 specially selected papers from the Fiftieth Annual ACM Symposium on Theory of Computing, otherwise known as STOC 2018, held June 25 to 29 in Los Angeles, California. The papers here were chosen to represent both the excellence and the broad range of the STOC program. The papers have been revised and extended by the authors and subjected to the standard thorough reviewing process of SICOMP. The program committee consisted of Dimitris Achlioptas (University of California, Santa Cruz), Dorit Aharonov (Hebrew University), Susanne Albers (Technical University Munich), Eric Allender (Rutgers University), Sayan Bhattacharya (University of Warwick), Richard Cole (New York University), Vitaly Feldman (Google Research), Uriel Feige (Weizmann Institute), Sanjam Garg (University of California, Berkeley), Ashish Goel (Stanford University), Parikshit Gopalan (VMware), Monika Henzinger, chair (University of Vienna), Giuseppe Italiano (Luiss University), Robert Kleinberg (Cornell University), Claire Matthieu (École Normale Supérieure, CNRS), Ankur Moitra (Massachusetts Institute of Technology), Danupon Nanongkai (KTH Royal Institute of Technology, Stockholm), Michał Pilipczuk (University of Warsaw), Krzysztof Pietrzak (Institute of Science and Technology, Austria), Aaron Sidford (Stanford University), Christian Sohler (Universität zu Köln), Prasad Tetali (Georgia Institute of Technology), Kunal Talwar (Apple), Luca Trevisan (Bocconi University), Thomas Vidick (California Institute of Technology), Emo Welzl (ETH Zurich), Philipp Woelfel (University of Calgary), David Woodruff (Carnegie Mellon University), and Mary Wootters (Stanford University). They selected 112 papers out of 416 submissions. We briefly describe the papers that appear here. In “Round Compression for Parallel Matching Algorithms,” Artur Czumaj, Jakub Ła̧cki, Aleksander Ma̧dry, Slobodan Mitrović, Krzysztof Onak, and Piotr Sankowski break the $O(\log n)$ round complexity bound for 2-approximating the maximum matching in near-linear memory regime of the massively parallel computation model. In “Smooth Heaps and a Dual View of Self-Adjusting Data Structures,” László Kozma and Thatchaphol Saranurak show a new correspondence between self-adjusting binary search trees (BSTs) and heaps. Using this connection they are able to transfer known lower bounds on BSTs to a general model of heaps as well as obtain a new, simple, and efficient heap algorithm called the “smooth heap.” In “Collusion Resistant Traitor Tracing from Learning with Errors," Rishab Goyal, Venkata Koppula, and Brent Waters introduce a new approach to the traitor tracing problem. Informally, in traitor tracing one aims to devise an encryption scheme such that decryption can be performed using $n$ different private keys and such that moreover any decryption can be “traced back" to the key(s) that was or were used for it. In this paper the authors obtain the first scheme with ciphertext size that grows polynomially in $\log(n)$ and the security parameter $\lambda$ and whose security is based on the learning with errors assumption. In “Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs,” Mark Braverman, Gil Cohen, and Sumegha Garg construct a hitting set for unrestricted read-once branching programs with seed length $O(\log^2n + \log(1/\varepsilon))$. This is the first improvement since Nisan's pseudorandom generator with seed length $O(\log^2n + \log n \log(1/\varepsilon)$. In “Circuit Lower Bounds for Nondeterministic Quasi-Polytime from a New Easy Witness Lemma,” Cody Murray and Ryan Williams show that if every problem in NP has polynomial-size circuits for a fixed polynomial, then every problem in NP also has a fixed polynomial-size witness. A specific consequence of this result is that for every fixed $k$, NQP does not have $n^{\log^k n}$-size ACC$\circ$THR circuits. In “Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds,” Kasper Green Larsen, Omri Weinstein, and Huacheng Yu prove the first superlogarithmic lower bounds on the cell probe complexity of dynamic Boolean data structure problems, a long-standing milestone in data structure lower bounds. In “Shadow Tomography of Quantum States,” Scott Aaronson asks: Given an unknown $D$-dimensional quantum mixed state $\rho$ and two-outcome measurements $E_1, \ldots, E_M$, how many copies of $\rho$ are needed to estimate the probability that $E_i$ accepts $\rho$ to within additive error $\varepsilon$, for each of the $M$ measurements? He shows that $O(\varepsilon^{-4} \log^4 M \log D)$ copies of $\rho$ suffice, implying, for example, that we can learn the behavior of an arbitrary $n$-qubit state, on all accepting/rejecting circuits of some fixed polynomial size, by measuring only $n^{O(1)}$ copies of the state. In “Inapproximability of the Independent Set Polynomial in the Complex Plane,” Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, and Daniel Štefankovič study the complexity of approximating the independent set polynomial of a graph with maximum degree $\Delta$ when the activity $\lambda$ is a complex number. They prove that outside a cardioid-shaped region in the complex plane identified by Peters and Regts, wherein the occupation ratios of $\Delta$-regular trees converge, approximation is $\#$P-hard (unless $\lambda$ is a positive real number, in which case it is NP-hard). In “A Friendly Smoothed Analysis of the Simplex Method,” Daniel Dadush and Sophie Huiberts consider linear programs with $d$ variables and $n$ constraints, smoothed by the addition of Gaussian noise with variance $\sigma^2$. They provide an improved and greatly simplified analysis of shadow simplex methods by combining an improved shadow bound with improvements on algorithmic techniques of Vershynin and show that in expectation $O(d^2 \sqrt{\log n} \, \sigma^{-2} + d^3 \log^{3/2}n)$ pivots suffice. In “Nearly Work-Efficient Parallel Algorithm for Digraph Reachability,” Jeremy T. Fineman presents a randomized parallel algorithm for digraph reachability and related problems with expected work $\tilde{O}(m)$ and span $\tilde{O}(n^{2/3})$. This is the first parallel algorithm having both nearly linear work and strongly sublinear span.

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.

We develop a framework for the rigorous analysis of focused stochastic local search algorithms. These algorithms search a state space by repeatedly selecting some constraint that is violated in the current state and moving to a random nearby state that addresses the violation, while (we hope) not introducing many new violations. An important class of focused local search algorithms with provable performance guarantees has recently arisen from algorithmizations of the Lovász local lemma (LLL), a nonconstructive tool for proving the existence of satisfying states by introducing a background measure on the state space. While powerful, the state transitions of algorithms in this class must be, in a precise sense, perfectly compatible with the background measure. In many applications this is a very restrictive requirement, and one needs to step outside the class. Here we introduce the notion of measure distortion and develop a framework for analyzing arbitrary focused stochastic local search algorithms, recovering LLL algorithmizations as the special case of no distortion. Our framework takes as input an arbitrary algorithm of such type and an arbitrary probability measure and shows how to use the measure as a yardstick of algorithmic progress, even for algorithms designed independently of the measure.

In recent years word-embedding models have gained great popularity due to their remarkable performance on several tasks, including word analogy questions and caption generation.An unexpected "sideeffect" of such models is that their vectors often exhibit compositionality, i.e., adding two word-vectors results in a vector that is only a small angle away from the vector of a word representing the semantic composite of the original words, e.g., "man" + "royal" = "king".

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

Spatially coupled codes have been shown to achieve the capacity for a large class of channels universally. Many variants of such codes have been introduced to date. We discuss a further such variant that is particularly simple and is determined by a very small number of parameters. More precisely, we consider and ensemble of time-invariant low-density parity-check convolutional codes with very large constraint lengths. We show via simulations that, despite their extreme simplicity, such codes still show the threshold saturation behavior known from the spatially coupled codes discussed in the literature. Further, we show how the size of the typical minimum stopping set is related to basic parameters of the code. Due to their simplicity and good performance, these codes might be attractive from an implementation perspective.

We report on a novel technique called spatial coupling and its application in the analysis of random constraint satisfaction problems (CSP). Spatial coupling was invented as an engineering construction in the area of error correcting codes where it has resulted in efficient capacity-achieving codes for a wide range of channels. However, this technique is not limited to problems in communications, and can be applied in the much broader context of graphical models. We describe here a general methodology for applying spatial coupling to random constraint satisfaction problems and obtain lower bounds for their (rough) satisfiability threshold. The main idea is to construct a distribution of geometrically structured random K-SAT instances – namely the spatially coupled ensemble – which has the same (rough) satisfiability threshold, and is at the same time algorithmically easier to solve. Then by running well-known algorithms on the spatially coupled ensemble we obtain a lower bound on the (rough) satisfiability threshold of the original ensemble. The method is versatile because one can choose the CSP, there is a certain amount of freedom in the construction of the spatially coupled ensemble, and also in the choice of the algorithm. In this work we focus on random K-SAT but we have also checked that the method is successful for Coloring, NAE-SAT and XOR-SAT. We choose Unit Clause propagation for the algorithm which is analyzed over the spatially coupled instances. For K = 3, for instance, our lower bound is equal to 3.67 which is better than the current bounds in the literature. Similarly, for graph 3-colorability we get a bound of 2.22 which is also better than the current bounds in the literature.

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.

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 Lovász 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 the inevitability of reaching a sink is established by bounding the entropy of the walk as a function of time.

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.

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.

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

Understanding the graph structure of the Internet is a crucial step for building accurate network models and designing efficient algorithms for Internet applications. Yet, obtaining this graph structure can be a surprisingly difficult task, as edges cannot be explicitly queried. For instance, empirical studies of the network of Internet Protocol (IP) addresses typically rely on indirect methods like traceroute to build what are approximately single-source, all-destinations, shortest-path trees. These trees only sample a fraction of the network's edges, and a paper by Lakhina et al. [2003] found empirically that the resulting sample is intrinsically biased. Further, in simulations, they observed that the degree distribution under traceroute sampling exhibits a power law even when the underlying degree distribution is Poisson. In this article, we study the bias of traceroute sampling mathematically and, for a very general class of underlying degree distributions, explicitly calculate the distribution that will be observed. As example applications of our machinery, we prove that 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.

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

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.

Given a matrix A , it is often desirable to find a good approximation to A that has low rank. We introduce a simple technique for accelerating the computation of such approximations when A has strong spectral features, that is, 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 nonzero 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 N to A , whose entries are independent random variables with zero-mean and bounded variance. Since, with high probability, N has very weak spectral features, we can prove that the effect of sampling and quantization nearly vanishes when a low-rank approximation to A + N is computed. We give high probability bounds on the quality of our approximation both in the Frobenius and the 2-norm.

Say that a k -CNF a formula is p-satisfiable if there exists a truth assignment satisfying a fraction 1 − 2 − k + p 2 − k of its clauses (note that every k -CNF formula is 0-satisfiable). Let F k ( n , m ) denote a random k -CNF formula on n variables with m clauses. For every k ≥2 and every r >0 we determine p and δ=δ( k )= O ( k 2 − k /2 ) such that with probability tending to 1 as n →∞, a random k -CNF formula F k ( n , rn ) is p -satisfiable but not ( p +δ)-satisfiable.

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.

Many NP‐complete constraint satisfaction problems appear to undergo a “phase transition” from solubility to insolubility when the constraint density passes through a critical threshold. In all such cases it is easy to derive upper bounds on the location of the threshold by showing that above a certain density the first moment (expectation) of the number of solutions tends to zero. We show that in the case of certain symmetric constraints, considering the second moment of the number of solutions yields nearly matching lower bounds for the location of the threshold. Specifically, we prove that the threshold for both random hypergraph 2‐colorability (Property B) and random Not‐All‐Equal k‐SAT is $2^{k-1}\ln 2 -O(1)$. As a corollary, we establish that the threshold for random k‐SAT is of order $\Theta(2^k)$, resolving a long‐standing open problem.

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.

The evaluation of incomplete satisfiability solvers depends critically on the availability of hard satisfiable instances. A plausible source of such instances consists of random k-SAT formulas whose clauses are chosen uniformly from among all clauses satisfying some randomly chosen truth assignment A. Unfortunately, instances generated in this manner tend to be relatively easy and can be solved efficiently by practical heuristics. Roughly speaking, for a number of different algorithms, A acts as a stronger and stronger attractor as the formula's density increases. Motivated by recent results on the geometry of the space of satisfying truth assignments of random k-SAT and NAE-k-SAT formulas, we introduce a simple twist on this basic model, which appears to dramatically increase its hardness. 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 compliment of A are satisfying. It appears that under this "symmetrization" the effects of the two attractors largely cancel out, making it much harder for algorithms to find any truth assignment. We give theoretical and experimental evidence supporting this assertion.

For every d > 0, let kd 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 kd or kd+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.

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.

Let Fk(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 ≥ 2k ln 2, Fk(n,rn) is unsatisfiable with probability 1-o(1). We prove that there exists a sequence tk = O(k) such that for r ≥ 2k ln 2 - tk, Fk(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.

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 rr/sub k/. It has long been known that 2/sup k//k2/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.

The technique of using di#erential 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.

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.

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

A 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 random k-dimensional hyperplane. We give a novel construction of the embedding, suitable for database applications, which amounts to computing a simple aggregate over k random attribute partitions.

We give the first example of a sharp threshold in proof complexity. More precisely, we show that for any sufficiently small � and � � �, random formulas consisting of 2-clauses and 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 2-clauses (and 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.

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.

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.

Let X be a set of n Boolean variables and denote by C(X) the set of all 3-clauses over X, i.e. the set of all 8(3) possible disjunctions of three distinct, non-complementary literais from variables in X. Let F(n, m) be a random 3-SAT formula formed by selecting, with replacement, m clauses uniformly at random from C(X) and taking their conjunction. The satisfiability threshold conjecture asserts that there exists a constant ra such that as n--+ c¢, F(n, rn) is satisfiable with probability that tends to 1 if r < ra, but unsatisfiable with probability that tends to 1 if r:> r3. Experimental evidence suggests rz ~ 4.2. We prove rz> 3.145 improving over the previous best lower bound r3> 3.003 due to Frieze and Suen. For this, we intro-duce a satisfiability heuristic that works iteratively, permanently setting the value of a pair of variables in each round. The framework we develop for the analysis of our heuristic allows us to also derive most previous lower bounds for random 3-SAT in a uniform manner and with little effort.

Directed st-connectivity is the problem of deciding whether or not there exists a path from a distinguished node s to a distinguished node t in a directed graph. We prove a time--space lower bound on the probabilistic NNJAG model of Poon [ Proc. 34th Annual Symposium on Foundations of Computer Science, Palo Alto, CA, 1993, pp. 218--227]. Let n be the number of nodes in the input graph and S and T be the space and time used by the NNJAG, respectively. We show that, for any $\delta > 0$, if an NNJAG uses space $S \in O(n^{1-\delta})$, then $T \in 2^{ \Omega(\log^2 (n/S)) }$; otherwise $T \in 2^{ \Omega( \log^2({n\log n \over S}) / \log\log n )} \times (nS / \log n)^{1/2}$. (In a preliminary version of this paper by Edmonds and Poon [Proc. 27th Annual ACM Symposium on Theory of Computing, Las Vegas, NV, 1995, pp. 147--156.], a lower bound of $T \in 2^{ \Omega( \log^2({n\log n \over S}) / \log\log n )} \times (nS/\log n)^{1/2}$ was proved.) Our result greatly improves the previous lower bound of $ST \in \Omega(n^2/\log n)$ on the JAG model by Barnes and Edmonds [ Proc. 34th Annual Symposium on Foundations of Computer Science, Palo Alto, CA, 1993, pp. 228--237] and that of $S^{1/3}T \in \Omega(n^{4/3})$ on the NNJAG model by Edmonds [ Time-Space Lower Bounds for Undirected and Directed ST-Connectivity on JAG Models, Ph.D. thesis, University of Toronto, Toronto, ON, Canada, 1993]. Our lower bound is tight for $S \in O(n^{1-\delta})$, for any $\delta > 0$, matching the upper bound of Barnes \etal [ Proc. 7th Annual IEEE Conference on Structure in Complexity Theory, Boston, MA, 1992, pp. 27--33]. As a corollary of this improved lower bound, we obtain the first tight space lower bound of $\Omega( \log^2 n )$ on the NNJAG model. No tight space lower bound was previously known even for the more restricted JAG model.

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.