A central theme in distributed network algorithms concerns understanding and coping with the issue of locality. Inspired by sequential complexity theory, we focus on a complexity theory for distributed decision problems. In the context of locality, solving a decision problem requires the processors to independently inspect their local neighborhoods and then collectively decide whether a given global input instance belongs to some specified language. This paper introduces several classes of distributed decision problems, proves separation among them and presents some complete problems. More specifically, we consider the standard LOCAL model of computation and define LD (for local decision) as the class of decision problems that can be solved in constant number of communication rounds. We first study the intriguing question of whether randomization helps in local distributed computing, and to what extent. Specifically, we define the corresponding randomized class BPLD, and ask whether LD=BPLD. We provide a partial answer to this question by showing that in many cases, randomization does not help for deciding hereditary languages. In addition, we define the notion of local many-one reductions, and introduce the (nondeterministic) class NLD of decision problems for which there exists a certificate that can be verified in constant number of communication rounds. We prove that there exists an NLD-complete problem. We also show that there exist problems not in NLD. On the other hand, we prove that the class NLD#n, which is NLD assuming that each processor can access an oracle that provides the number of nodes in the network, contains all (decidable) languages. For this class we provide a natural complete problem as well.
The question of whether randomization helps in decreasing the locality parameter of construction problems has been the focus of numerous studies. To date, there exists evidence that, for some problems at least, randomization does not help. For instance, @cite_30 proves this for 3-coloring the ring. In fact, for low degree graphs, the gaps between the efficiencies of the best known randomized and deterministic algorithms for problems like MIS, @math -coloring, and Maximal Matching are very small. On the other hand, for graphs of arbitrarily large degrees, there seem to be indications that randomization does help, at least in some cases. For instance, @math -coloring can be randomly computed in expected @math communication rounds on @math -node graphs @cite_39 @cite_6 , whereas the best known deterministic algorithm for this problem performs in @math rounds @cite_1 . @math -coloring results whose performances are measured also with respect to the maximum degree @math illustrate this phenomena as well. Specifically, @cite_27 shows that @math -coloring can be randomly computed in expected @math communication rounds whereas the best known deterministic algorithm performs in @math rounds @cite_40 @cite_24 .
@cite_30 @cite_1 @cite_6 @cite_39 @cite_24 @cite_27 @cite_40
2279830512 2552279664 2478193891 2046633098 2115831572 2607483562 2797253418 1610636547 2088272899 2065826935 2951290586 1975579567 2157562188 2067202579 2534944111 2072211488 2626796510 1980130379 1970330908 2150516767
Over the past 30 years numerous algorithms have been designed for symmetry breaking problems in the LOCAL model, such as maximal matching, MIS, vertex coloring, and edge-coloring. For most problems the best randomized algorithm is at least exponentially faster than the best deterministic algorithm. In this paper we prove that these exponential gaps are necessary and establish connections between the deterministic and randomized complexities in the LOCAL model. Each result has a very compelling take-away message: 1. Fast @math -coloring of trees requires random bits: Building on the recent lower bounds of , we prove that the randomized complexity of @math -coloring a tree with maximum degree @math is @math , whereas its deterministic complexity is @math for any @math . This also establishes a large separation between the deterministic complexity of @math -coloring and @math -coloring trees. 2. Randomized lower bounds imply deterministic lower bounds: We prove that any deterministic algorithm for a natural class of problems that runs in @math rounds can be transformed to run in @math rounds. If the transformed algorithm violates a lower bound (even allowing randomization), then one can conclude that the problem requires @math time deterministically. 3. Deterministic lower bounds imply randomized lower bounds: We prove that the randomized complexity of any natural problem on instances of size @math is at least its deterministic complexity on instances of size @math . This shows that a deterministic @math lower bound for any problem implies a randomized @math lower bound. It also illustrates that the graph shattering technique is absolutely essential to the LOCAL model. This paper is centered on the complexity of graph problems in the well-studied LOCAL model of distributed computing, introduced by Linial [FOCS '87]. It is widely known that for many of the classic distributed graph problems (including maximal independent set (MIS) and (Δ+1)-vertex coloring), the randomized complexity is at most polylogarithmic in the size n of the network, while the best deterministic complexity is typically 2O(√logn). Understanding and potentially narrowing down this exponential gap is considered to be one of the central long-standing open questions in the area of distributed graph algorithms. We investigate the problem by introducing a complexity-theoretic framework that allows us to shed some light on the role of randomness in the LOCAL model. We define the SLOCAL model as a sequential version of the LOCAL model. Our framework allows us to prove completeness results with respect to the class of problems which can be solved efficiently in the SLOCAL model, implying that if any of the complete problems can be solved deterministically in logn rounds in the LOCAL model, we can deterministically solve all efficient SLOCAL-problems (including MIS and (Δ+1)-coloring) in logn rounds in the LOCAL model. Perhaps most surprisingly, we show that a rather rudimentary looking graph coloring problem is complete in the above sense: Color the nodes of a graph with colors red and blue such that each node of sufficiently large polylogarithmic degree has at least one neighbor of each color. The problem admits a trivial zero-round randomized solution. The result can be viewed as showing that the only obstacle to getting efficient determinstic algorithms in the LOCAL model is an efficient algorithm to approximately round fractional values into integer values. In addition, our formal framework also allows us to develop polylogarithmic-time randomized distributed algorithms in a simpler way. As a result, we provide a polylog-time distributed approximation scheme for arbitrary distributed covering and packing integer linear programs. This paper addresses the cornerstone family of in distributed computing, and investigates the curious gap between randomized and deterministic solutions under bandwidth restrictions. Our main contribution is in providing tools for derandomizing solutions to local problems, when the @math nodes can only send @math -bit messages in each round of communication. We combine bounded independence, which we show to be sufficient for some algorithms, with the method of conditional expectations and with additional machinery, to obtain the following results. Our techniques give a deterministic maximal independent set (MIS) algorithm in the CONGEST model, where the communication graph is identical to the input graph, in @math rounds, where @math is the diameter of the graph. The best known running time in terms of @math alone is @math , which is super-polylogarithmic, and requires large messages. For the CONGEST model, the only known previous solution is a coloring-based @math -round algorithm, where @math is the maximal degree in the graph. On the way to obtaining the above, we show that in the model, which allows all-to-all communication, there is a deterministic MIS algorithm that runs in @math rounds. , where @math is the maximum degree. When @math , the bound improves to @math and holds also for @math -coloring. In addition, we deterministically construct a @math -spanner with @math edges in @math rounds. For comparison, in the more stringent CONGEST model, the best deterministic algorithm for constructing a @math -spanner with @math edges runs in @math rounds. We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has to be conflict-free, in the sense that in every interval I there is a color that appears exactly once in I. We present several deterministic and randomized algorithms for achieving this goal, and analyze their performance, that is, the maximum number of colors that they need to use, as a function of the number n of inserted points. We first show that a natural and simple (deterministic) approach may perform rather poorly, requiring Ω(√n) colors in the worst case. We then modify this approach, to obtain an efficient deterministic algorithm that uses a maximum of Θ(log2 n) colors. Next, we present two randomized solutions. The first algorithm requires an expected number of at most O(log2 n) colors, and produces a coloring which is valid with high probability, and the second one, which is a variant of our efficient deterministic algorithm, requires an expected number of at most O(log n log log n) colors but always produces a valid coloring. We also analyze the performance of the simplest proposed algorithm when the points are inserted in a random order, and present an incomplete analysis that indicates that, with high probability, it uses only O(log n) colors. Finally, we show that in the extension of this problem to two dimensions, where the relevant ranges are disks, n colors may be required in the worst case. The average-case behavior for disks, and cases involving other planar ranges, are still open. 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. We present a deterministic distributed algorithm that computes a (2&#x03B4;-1)-edge-coloring, or even list-edge-coloring, in any n-node graph with maximum degree &#x03B4;, in O(log^8 &#x03B4; &#x22C5; log n) rounds. This answers one of the long-standing open questions of distributed graph algorithms from the late 1980s, which asked for a polylogarithmic-time algorithm. See, e.g., Open Problem 4 in the Distributed Graph Coloring book of Barenboim and Elkin. The previous best round complexities were 2^ O(&#x221A; log n ) by Panconesi and Srinivasan [STOC92] and &#x00D5;(&#x221A; &#x03B4; ) + O(log^* n) by Fraigniaud, Heinrich, and Kosowski [FOCS16]. A corollary of our deterministic list-edge-coloring also improves the randomized complexity of (2&#x03B4;-1)-edge-coloring to poly(loglog n) rounds.The key technical ingredient is a deterministic distributed algorithm for hypergraph maximal matching, which we believe will be of interest beyond this result. In any hypergraph of rank r &#x2014; where each hyperedge has at most r vertices &#x2014; with n nodes and maximum degree &#x03B4;, this algorithm computes a maximal matching in O(r^5 log^ 6+log r &#x03B4; &#x22C5; log n) rounds.This hypergraph matching algorithm and its extensions also lead to a number of other results. In particular, we obtain a polylogarithmic-time deterministic distributed maximal independent set (MIS) algorithm for graphs with bounded neighborhood independence, hence answering Open Problem 5 of Barenboim and Elkins book, a ((log &#x03B4; &#x03B5;)^ O(log 1 &#x03B5;) )-round deterministic algorithm for (1+&#x03B5;)-approximation of maximum matching, and a quasi-polylogarithmic-time deterministic distributed algorithm for orienting &#x03BB;-arboricity graphs with out-degree at most (1+&#x03B5;)&#x03BB; , for any constant &#x03B5; 0, hence partially answering Open Problem 10 of Barenboim and Elkins book. We give a new randomized distributed algorithm for (Δ +1)-coloring in the LOCAL model, running in O(s log Δ)+ 2O(slog log n) rounds in a graph of maximum degree Δ. This implies that the (Δ +1)-coloring problem is easier than the maximal independent set problem and the maximal matching problem, due to their lower bounds of Ω(min(sflog n log log n, flog Δ log log Δ)) by Kuhn, Moscibroda, and Wattenhofer [PODC’04]. Our algorithm also extends to list-coloring where the palette of each node contains Δ +1 colors. We extend the set of distributed symmetry-breaking techniques by performing a decomposition of graphs into dense and sparse parts. For many random constraint satisfaction problems such as random satisfiability or random graph or hypergraph coloring, the best current estimates of the threshold for the existence of solutions are based on the first and the second moment method. However, in most cases these techniques do not yield matching upper and lower bounds. Sophisticated but non-rigorous arguments from statistical mechanics have ascribed this discrepancy to the existence of a phase transition called condensation that occurs shortly before the actual threshold for the existence of solutions and that affects the combinatorial nature of the problem (Krzakala, Montanari, Ricci-Tersenghi, Semerjian, Zdeborova: PNAS 2007). In this paper we prove for the first time that a condensation transition exists in a natural random CSP, namely in random hypergraph 2-coloring. Perhaps surprisingly, we find that the second moment method applied to the number of 2-colorings breaks down strictly before the condensation transition. Our proof also yields slightly improved bounds on the threshold for random hypergraph 2-colorability. The problem of coloring a graph with the minimum number of colors is well known to be NP-hard, even restricted to k-colorable graphs for constant k ≥ 3. On the other hand, it is known that random k-colorable graphs are easy to k-color. The algorithms for coloring random k-colorable graphs require fairly high edge densities, however. In this paper we present algorithms that color randomly generated k-colorable graphs for much lower edge densities than previous approaches. In addition, to study a wider variety of graph distributions, we also present a model of graphs generated by the semi-random source of Santha and Vazirani (M. Santha and U. V. Vazirani, J. Comput. System Sci.33 (1986), 75-87) that provides a smooth transition between the worst-case and random models. In this model, the graph is generated by a "noisy adversary"-an adversary whose decisions (whether or not to insert a particular edge) have some small (random) probability of being reversed. We show that even for quite low noise rates, semi-random k-colorable graphs can be optimally colored with high probability. Consider an n-vertex graph G = (V, E) of maximum degree Δ, and suppose that each vertex v ∈ V hosts a processor. The processors are allowed to communicate only with their neighbors in G. The communication is synchronous, that is, it proceeds in discrete rounds. In the distributed vertex coloring problem, the objective is to color G with Δ + 1, or slightly more than Δ + 1, colors using as few rounds of communication as possible. (The number of rounds of communication will be henceforth referred to as running time.) Efficient randomized algorithms for this problem are known for more than twenty years [ 1986; Luby 1986]. Specifically, these algorithms produce a (Δ + 1)-coloring within O(log n) time, with high probability. On the other hand, the best known deterministic algorithm that requires polylogarithmic time employs O(Δ2) colors. This algorithm was devised in a seminal FOCS’87 paper by Linial [1987]. Its running time is O(log* n). In the same article, Linial asked whether one can color with significantly less than Δ2 colors in deterministic polylogarithmic time. By now, this question of Linial became one of the most central long-standing open questions in this area. In this article, we answer this question in the affirmative, and devise a deterministic algorithm that employs Δ1+o(1) colors, and runs in polylogarithmic time. Specifically, the running time of our algorithm is O(f(Δ)log Δ log n), for an arbitrarily slow-growing function f(Δ) = ω(1). We can also produce an O(Δ1+η)-coloring in O(log Δ log n)-time, for an arbitrarily small constant η > 0, and an O(Δ)-coloring in O(Δe log n) time, for an arbitrarily small constant e > 0. Our results are, in fact, far more general than this. In particular, for a graph of arboricity a, our algorithm produces an O(a1+η)-coloring, for an arbitrarily small constant η > 0, in time O(log a log n). The paper tackles the power of randomization in the context of locality by analyzing the ability to boost' the success probability of deciding a distributed language. The main outcome of this analysis is that the distributed computing setting contrasts significantly with the sequential one as far as randomization is concerned. Indeed, we prove that in some cases, the ability to increase the success probability for deciding distributed languages is rather limited. Informally, a (p,q)-decider for a language L is a distributed randomized algorithm which accepts instances in L with probability at least p and rejects instances outside of L with probability at least q. It is known that every hereditary language that can be decided in t rounds by a (p,q)-decider, where p^2+q>1, can actually be decided deterministically in O(t) rounds. In one of our results we give evidence supporting the conjecture that the above statement holds for all distributed languages. This is achieved by considering the restricted case of path topologies. We then turn our attention to the range below the aforementioned threshold, namely, the case where p^2+q . We define B_k(t) to be the set of all languages decidable in at most t rounds by a (p,q)-decider, where p^ 1+1 k +q>1. It is easy to see that every language is decidable (in zero rounds) by a (p,q)-decider satisfying p+q=1. Hence, the hierarchy B_k provides a spectrum of complexity classes between determinism and complete randomization. We prove that all these classes are separated: for every integer k 1, there exists a language L satisfying L B_ k+1 (0) but L B_k(t) for any t=o(n). In addition, we show that B_ (t) does not contain all languages, for any t=o(n). Finally, we show that if the inputs can be restricted in certain ways, then the ability to boost the success probability becomes almost null. In this paper, we carry on investigating the line of research questioning the power of randomization for the design of distributed algorithms. In their seminal paper, Naor and Stockmeyer [STOC 1993] established that, in the context of network computing, in which all nodes execute the same algorithm in parallel, any construction task that can be solved locally by a randomized Monte-Carlo algorithm can also be solved locally by a deterministic algorithm. This result however holds in a specific context. In particular, it holds only for distributed tasks whose solutions can be locally checked by a deterministic algorithm. In this paper, we extend the result of Naor and Stockmeyer to a wider class of tasks. Specifically, we prove that the same derandomization result holds for every task whose solutions can be locally checked using a 2-sided error randomized Monte-Carlo algorithm. This extension finds applications to, e.g., the design of lower bounds for construction tasks which tolerate that some nodes compute incorrect values. In a nutshell, we show that randomization does not help for solving such resilient tasks. We study deterministic, distributed algorithms for two weak variants of the standard graph coloring problem. We consider defective colorings, i.e., colorings where nodes of a color class may induce a graph of maximum degree d for some parameter d>0. We also look at colorings where a minimum number of multi-chromatic edges is required. For an integer k>0, we call a coloring k-partially proper if every node v has at least min k,deg(v) neighbors with a different color. We show that for all d∈ 1,...,Δ , it is possible to compute a O(Δ2 d2)-coloring with defect d in time O(log*n) where Δ is the largest degree of the network graph. Similarly, for all k∈ 1,...,Δ , a k-partially proper O(k2)-coloring can be computed in O(log*n) rounds. As an application of our weak defective coloring algorithm, we obtain a faster deterministic algorithm for the standard vertex coloring problem on graphs with moderate degrees. We show that in time O(Δ+log*n), a (Δ+1)-coloring can be computed, a task for which the best previous algorithm required time O(Δ*log(Δ) + log*n). The same result holds for the problem of computing a maximal independent set. A central theme in distributed network algorithms concerns understanding and coping with the issue of locality . Despite considerable progress, research efforts in this direction have not yet resulted in a solid basis in the form of a fundamental computational complexity theory for locality. Inspired by sequential complexity theory, we focus on a complexity theory for . In the context of locality, solving a decision problem requires the processors to independently inspect their local neighborhoods and then collectively decide whether a given global input instance belongs to some specified language. We consider the standard @math model of computation and define @math (for local decision ) as the class of decision problems that can be solved in @math communication rounds. We first study the intriguing question of whether randomization helps in local distributed computing, and to what extent. Specifically, we define the corresponding randomized class @math , containing all languages for which there exists a randomized algorithm that runs in @math rounds, accepts correct instances with probability at least @math and rejects incorrect ones with probability at least @math . We show that @math is a threshold for the containment of @math in @math . More precisely, we show that there exists a language that does not belong to @math for any @math but does belong to @math for any @math such that @math . On the other hand, we show that, restricted to hereditary languages, @math , for any function @math and any @math such that @math . In addition, we investigate the impact of non-determinism on local decision, and establish some structural results inspired by classical computational complexity theory. Specifically, we show that non-determinism does help, but that this help is limited, as there exist languages that cannot be decided non-deterministically. Perhaps surprisingly, it turns out that it is the combination of randomization with non-determinism that enables to decide languages . Finally, we introduce the notion of local reduction, and establish some completeness results. We study a family of closely-related distributed graph problems, which we call degree splitting, where roughly speaking the objective is to partition (or orient) the edges such that each node's degree is split almost uniformly. Our findings lead to answers for a number of problems, a sampling of which includes: • We present a poly log n round deterministic algorithm for (2Δ−1)·(1+o(1))-edge-coloring, where Δ denotes the maximum degree. Modulo the 1 + o(1) factor, this settles one of the long-standing open problems of the area from the 1990's (see e.g. Panconesi and Srinivasan [PODC'92]). Indeed, a weaker requirement of (2Δ − 1) · poly log Δ-edge-coloring in poly log n rounds was asked for in the 4th open question in the Distributed Graph Coloring book by Barenboim and Elkin. • We show that sinkless orientation---i.e., orienting edges such that each node has at least one out-going edge---on Δ-regular graphs can be solved in O(logΔ log n) rounds randomized and in O(logΔ n) rounds deterministically. These prove the corresponding lower bounds by [STOC'16] and Chang, Kopelowitz, and Pettie [FOCS'16] to be tight. Moreover, these show that sinkless orientation exhibits an exponential separation between its randomized and deterministic complexities, akin to the results of for Δ-coloring Δ-regular trees. • We present a randomized O(log4 n) round algorithm for orienting a-arboricity graphs with maximum out-degree a(1 + e). This can be also turned into a decomposition into a(1 + e) forests when a = Ω(log n) and into a(1 + e) pseduo-forests when a = o(log n). Obtaining an efficient distributed decomposition into less than 2a forests was stated as the 10th open problem in the book by Barenboim and Elkin. Abstract The paper studies effective approximate solutions to combinatorial counting and unform generation problems. Using a technique based on the simulation of ergodic Markov chains, it is shown that, for self-reducible structures, almost uniform generation is possible in polynomial time provided only that randomised approximate counting to within some arbitrary polynomial factor is possible in polynomial time. It follows that, for self-reducible structures, polynomial time randomised algorithms for counting to within factors of the form (1 + n − β ) are available either for all β ϵ R or for no β ϵ R . A substantial part of the paper is devoted to investigating the rate of convergence of finite ergodic Markov chains, and a simple but powerful characterisation of rapid convergence for a broad class of chains based on a structural property of the underlying graph is established. Finally, the general techniques of the paper are used to derive an almost uniform generation procedure for labelled graphs with a given degree sequence which is valid over a much wider range of degrees than previous methods: this in turn leads to randomised approximate counting algorithms for these graphs with very good asymptotic behaviour. In the standard CONGEST model for distributed network computing, it is known that "global" tasks such as minimum spanning tree, diameter, and all-pairs shortest paths, consume large bandwidth, for their running-time is @math rounds in @math -node networks with constant diameter. Surprisingly, "local" tasks such as detecting the presence of a 4-cycle as a subgraph also requires @math rounds, even using randomized algorithms, and the best known upper bound for detecting the presence of a 3-cycle is @math rounds. The objective of this paper is to better understand the landscape of such subgraph detection tasks. We show that, in contrast to , which are hard to detect in the CONGEST model, there exists a deterministic algorithm for detecting the presence of a subgraph isomorphic to @math running in a number of rounds, for every tree @math . Our algorithm provides a distributed implementation of a combinatorial technique due to Erd o for sparsening the set of partial solutions kept by the nodes at each round. Our result has important consequences to , i.e., to randomized algorithms whose aim is to distinguish between graphs satisfying a property, and graphs far from satisfying that property. In particular, we get that, for every graph pattern @math composed of an edge and a tree connected in an arbitrary manner, there exists a distributed testing algorithm for @math -freeness, performing in a constant number of rounds. Although the class of graph patterns @math formed by a tree and an edge connected arbitrarily may look artificial, all previous results of the literature concerning testing @math -freeness for classical patterns such as cycles and cliques can be viewed as direct consequences of our result, while our algorithm enables testing more complex patterns. We study the graph coloring problem over random graphs of finite average connectivity c. Given a number q of available colors, we find that graphs with low connectivity admit almost always a proper coloring whereas graphs with high connectivity are uncolorable. Depending on q, we find with a one-step replica-symmetry breaking approximation the precise value of the critical average connectivity @math Moreover, we show that below @math there exists a clustering phase @math in which ground states spontaneously divide into an exponential number of clusters. Furthermore, we extended our considerations to the case of single instances showing consistent results. This leads us to propose a different algorithm that is able to color in polynomial time random graphs in the hard but colorable region, i.e., when @math Suppose that n processors are arranged in a ring and can communicate only with their immediate neighbors. It is shown that any probabilistic algorithm for 3 coloring the ring must take at least @math rounds, otherwise the probability that all processors are colored legally is less than @math . A similar time bound holds for selecting a maximal independent set. The bound is tight (up to a constant factor) in light of the deterministic algorithms of Cole and Vishkin [Inform, and Control, 70 (1986), pp. 32–53] and extends the lower bound for deterministic algorithms of Linial [Proc. 28th IEEE Foundations of Computer Science Symposium, 1987, pp. 331–335]. We use random sampling as a tool for solving undirected graph problems. We show that the sparse graph, or skeleton, that arises when we randomly sample a graph's edges will accurately approximate the value of all cuts in the original graph with high probability. This makes sampling effective for problems involving cuts in graphs. We present fast randomized (Monte Carlo and Las Vegas) algorithms for approximating and exactly finding minimum cuts and maximum flows in unweighted, undirected graphs. Our cut-approximation algorithms extend unchanged to weighted graphs while our weighted-graph flow algorithms are somewhat slower. Our approach gives a general paradigm with potential applications to any packing problem. It has since been used in a near-linear time algorithm for finding minimum cuts, as well as faster cut and flow algorithms. Our sampling theorems also yield faster algorithms for several other cut-based problems, including approximating the best balanced cut of a graph, finding a k-connected orientation of a 2k-connected graph, and finding integral multicommodity flows in graphs with a great deal of excess capacity. Our methods also improve the efficiency of some parallel cut and flow algorithms. Our methods also apply to the network design problem, where we wish to build a network satisfying certain connectivity requirements between vertices. We can purchase edges of various costs and wish to satisfy the requirements at minimum total cost. Since our sampling theorems apply even when the sampling probabilities are different for different edges, we can apply randomized rounding to solve network design problems. This gives approximation algorithms that guarantee much better approximations than previous algorithms whenever the minimum connectivity requirement is large. As a particular example, we improve the best approximation bound for the minimum k-connected subgraph problem from 1.85 to [math not displayed].