We study the intersection of a random geometric graph with an Erdős–Rényi graph. Specifically, we generate the random geometric graph G ( n , r ) by choosing n points uniformly at random from D = [ 0 , 1 ] 2 and joining any two points whose Euclidean distance is at most r . We let G ( n , p ) be the classical Erdős–Rényi graph, i.e. it has n vertices and every pair of vertices is adjacent with probability p independently. In this note we study G ( n , r , p ) ≔ G ( n , r ) ∩ G ( n , p ) . One way to think of this graph is that we take G ( n , r ) and then randomly delete edges with probability 1 − p independently. We consider the clique number, independence number, connectivity, Hamiltonicity, chromatic number, and diameter of this graph where both p ( n ) → 0 and r ( n ) → 0 ; the same model was studied by Kahle et al. (2023) for r ( n ) → 0 but p fixed.

We consider a simple model of a growing cluster of points in R d , d ≥ 2 . Beginning with a point X 1 located at the origin, we generate a random sequence of points X 1 , X 2 , … , X i , … , . To generate X i , i ≥ 2 we choose a uniform integer j in [ i − 1 ] = 1 , 2 , … , i − 1 and then let X i = X j + D i where D i = ( δ 1 , … , δ d ) . Here the δ j are independent copies of the Normal distribution N ( 0 , σ i ) , where σ i = i − α for some α > 0 . We prove that for any α > 0 the resulting point set is bounded a.s., and moreover, that the points generated look like samples from a β -dimensional subset of R d from the standpoint of the minimum lengths of combinatorial structures on the point-sets, where β = min ( d , 1 / α ) .

Abstract. We study the existence of a directed Hamilton cycle in random digraphs with [Formula: see text] edges where we condition on minimum in- and out-degree at least one. Denote such a random graph by [Formula: see text]. We prove that if [Formula: see text] then [Formula: see text]

The random walk d-ary cuckoo hashing algorithm was defined by Fotakis, Pagh, Sanders, and Spirakis to generalize and improve upon the standard cuckoo hashing algorithm of Pagh and Rodler. Random walk d-ary cuckoo hashing has low space overhead, guaranteed fast access, and fast in practice insertion time. In this paper, we give a theoretical insertion time bound for this algorithm. More precisely, for every$d\geq 3$hashes, let$c_{d}^{*}$be the sharp threshold for the load factor at which a valid assignment of$cm$objects to a hash table of size$m$likely exists. We show that for any$d\geq 4$hashes and load factor$c < c_{d}^{*}$, the expectation of the random walk insertion time is$O(1)$, that is, a constant depending only on$d$and$c$but not$m$.

Abstract. Given a graph [Formula: see text] on [Formula: see text] vertices and an assignment of colors to its edges, a set of edges [Formula: see text] is said to be rainbow if edges from [Formula: see text] have pairwise different colors assigned to them. In this paper, we investigate rainbow spanning trees in randomly colored random [Formula: see text] graphs.

Abstract. We extend a recent breakthrough result relating expectation thresholds and actual thresholds to include some rainbow versions.

Abstract. We estimate the likely values of the chromatic and independence numbers of the random [Formula: see text]-uniform [Formula: see text]-regular hypergraph on [Formula: see text] vertices for fixed [Formula: see text], large fixed [Formula: see text], and [Formula: see text].

Abstract. We present a rigorous and precise analysis of the maximum degree and the average degree in a dynamic duplication-divergence graph model introduced by Solé et al. [ Adv. Complex Syst., 5 (2002), pp. 43–54] in which the graph grows according to a duplication-divergence mechanism, i.e., by iteratively creating a copy of some node and then randomly alternating the neighborhood of a new node with probability [Formula: see text]. This model captures the growth of some real-world processes, e.g., biological or social networks. In this paper, we prove that for some [Formula: see text], the maximum degree and the average degree of a duplication-divergence graph on [Formula: see text] vertices are asymptotically concentrated with high probability around [Formula: see text] and [Formula: see text], respectively, i.e., they are within at most a polylogarithmic factor from these values with probability at least [Formula: see text] for any constant [Formula: see text].

We consider the problem of generating uniformly random partitions of the vertex set of a graph such that every piece induces a connected subgraph. For the case where we want to have partitions with linearly many pieces of bounded size, we obtain approximate sampling algorithms based on Glauber dynamics which are fixed-parameter tractable with respect to the bandwidth of G, with simple-exponential dependence on the bandwidth. For example, for rectangles of constant or logarithmic width this gives polynomial-time sampling algorithms. More generally, this gives sub-exponential algorithms for bounded-degree graphs without large expander sub-graphs (for example, we obtain time algorithms for square grids). In the case where we instead want partitions with a small number of pieces of linear size, we show that Glauber dynamics can have exponential mixing time, even just for the case of 2 pieces, and even for 2-connected sub-graphs of the grid with bounded bandwidth.

Abstract. Given an [Formula: see text] vertex graph whose edges have colored from one of [Formula: see text] colors [Formula: see text], we define the Hamilton cycle color profile [Formula: see text] to be the set of vectors [Formula: see text] such that there exists a Hamilton cycle that is the concatenation of [Formula: see text] paths [Formula: see text], where [Formula: see text] contains [Formula: see text] edges of color [Formula: see text]. We study [Formula: see text] when the edges are randomly colored. We discuss the profile close to the threshold for the existence of a Hamilton cycle and the threshold for when [Formula: see text].

We consider three central problems in optimization: the restricted assignment load-balancing problem, the Steiner tree network design problem, and facility location clustering. We consider the online setting, where the input arrives over time, and irrevocable decisions must be made without knowledge of the future. For all these problems, any online algorithm must incur a cost that is approximately $\log |I|$ times the optimal cost in the worst-case, where $|I|$ is the length of the input. But can we go beyond the worst-case? In this work we give algorithms that perform substantially better when a $p$-fraction of the input is given as a sample: the algorithm use this sample to \emph{learn} a good strategy to use for the rest of the input.

We consider the rank of a class of sparse Boolean matrices of size $n \times n$. In particular, we show that the probability that such a matrix has full rank, and is thus invertible, is a positive constant with value about 0.2574 for large $n$. The matrices arise as the vertex-edge incidence matrix of 1-out 3-uniform hypergraphs. The result that the null space is bounded in expectation can be contrasted with results for the usual models of sparse Boolean matrices, based on the vertex-edge incidence matrix of random $k$-uniform hypergraphs. For this latter model, the expected co-rank is linear in the number of vertices $n$, [A. Coja-Oghlan et al., in Proceedings of SODA, 2020, pp. 579--591], [C. Cooper, A. M. Frieze, and W. Pegden, in Proceedings of SODA, 2019, pp. 946--955]. For fields of higher order, the co-rank is typically Poisson distributed.

Let $p=\frac{1+\varepsilon}{n}$. It is known that if $N=\varepsilon^3n\to\infty$, then with high probability (w.h.p.) $G_{n,p}$ has a unique giant largest component. We show that if in addition, $\varepsilon=\varepsilon(n)\to 0$, then w.h.p. the cover time of $G_{n,p}$ is asymptotic to $n\log^2N$; previously Barlow, Ding, Nachmias, and Peres had shown this up to constant multiplicative factors.

We consider a constrained version of the shortest path problem on the complete graphs whose edges have independent random lengths and costs. We establish the asymptotic value of the minimum length as a function of the cost-budget within a wide range.

We study the isomorphism problem for random hypergraphs. We show that it is solvable in polynomial time for the binomial random k-uniform hypergraph Hn,p;k, for a wide range of p. We also show that it is solvable w.h.p. for random r-regular, k-uniform hypergraphs Hn,r;k,r=O(1).

We study the Hamiltonicity of the following model of a random graph. Suppose that we partition $[n]$ into $V_1,V_2,\ldots,V_k$ and add edge $\{x,y\}$ to our graph with probability $p$ if there exists $i$ such that $x,y\in V_i$. Otherwise, we add the edge with probability $q$. We denote this model by ${\mathcal G}({\bf n}, p,q)$ and give tight results for Hamiltonicity, including a critical window analysis, under various conditions.

We consider the following question. We have a dense regular graph $G$ with degree $\alpha n$, where $\alpha>0$ is a constant. We add $m=o(n^2)$ random edges. The edges of the augmented graph $G(m)$ are given independent edge weights $X(e),e\in E(G(m))$. We estimate the minimum weight of some specified combinatorial structures. We show that in certain cases, we can obtain the same estimate as is known for the complete graph but scaled by a factor $\alpha^{-1}$. We consider spanning trees, shortest paths, and perfect matchings in (pseudorandom) bipartite graphs.

We study the minimum spanning tree problem on the complete graph where an edge e has a weight We and a cost Ce, each of which is an independent uniform [0, 1] random variable. There is also a constraint that the spanning tree T must satisfy C(T) ≤ c0. We establish the asymptotic value of the optimum weight via the consideration of a dual problem. The proof is therefore constructive i.e. can be thought of as the analysis of a polynomial time algorithm. We also study the minimum spanning arborescence problem on the complete digraph where an edge e has a weight We and a cost Ce, each of which is an independent uniform [0, 1] random variable. There is also a constraint that the spanning arborescence T must satisfy C(T) ≤ c0. We establish the asymptotic value of the optimum weight via the consideration of a dual problem. The proof is via the analysis of a polynomial time algorithm.

We study the component structure of the random graph $G=G_{n,m,d}$. Here $d=O(1)$ and $G$ is sampled uniformly from ${\mathcal G}_{n,m,d}$, the set of graphs with vertex set $[n]$, $m$ edges, and maximum degree at most $d$. If $m=\mu n/2$, then we establish a threshold value $\mu_\star$ such that if $\mu<\mu_\star$, then with high probability (w.h.p.) the maximum component size is $O(\log n)$. If $\mu>\mu_\star$, then w.h.p. there is a unique giant component of order $n$ and the remaining components have size $O( \log n)$.

Let $Ω_q=Ω_q(H)$ denote the set of proper $[q]$-colorings of the hypergraph $H$. Let $Γ_q$ be the graph with vertex set $Ω_q$ and an edge ${σ,τ\}$ where $σ,τ$ are colorings iff $h(σ,τ)=1$. Here $h(σ,τ)$ is the Hamming distance $|\{v\in V(H):σ(v)\neqτ(v)\}|$. We show that if $H=H_{n,m;k},\,k\geq 2$, the random $k$-uniform hypergraph with $V=[n]$ and $m=dn/k$ then w.h.p. $Γ_q$ is connected if $d$ is sufficiently large and $q\gtrsim (d/\log d)^{1/(k-1)}$.

We consider the rank of a class of sparse Boolean matrices of size $n \times n$. In particular, we show that the probability that such a matrix has full rank, and is thus invertible, is a positive constant with value about 0.2574 for large $n$. The matrices arise as the vertex-edge incidence matrix of 1-out 3-uniform hypergraphs. The result that the null space is bounded in expectation can be contrasted with results for the usual models of sparse Boolean matrices, based on the vertex-edge incidence matrix of random $k$-uniform hypergraphs. For this latter model, the expected co-rank is linear in the number of vertices $n$, [A. Coja-Oghlan et al., in Proceedings of SODA, 2020, pp. 579--591], [C. Cooper, A. M. Frieze, and W. Pegden, in Proceedings of SODA, 2019, pp. 946--955]. For fields of higher order, the co-rank is typically Poisson distributed.

We consider the existence of patterned Hamilton cycles in randomly colored random graphs. Given a string $\Pi$ over a set of colors $\{1,2,\ldots,r\}$, we say that a Hamilton cycle is $\Pi$-colored if the pattern repeats at intervals of length $|\Pi|$ as we go around the cycle. We prove a hitting time result for the existence of such a cycle. We also prove a hitting time result for the related notion of $\Pi$-connected.

The game of plates and olives was originally formulated by Nicolaescu and encodes the evolution of the topology of the sublevel sets of Morse functions. We consider a random variant of this game. The process starts with an empty table. There are four different types of moves: (1) add a new plate to the table, (2) combine two plates and their olives onto one plate, removing the second plate from the table, (3) add an olive to a plate, and (4) remove an olive from a plate. We show that with high probability the number of olives is linear as the total number of moves goes to infinity. Furthermore, we prove that the number of olives is concentrated around its expectation.

We study a random walk that prefers tou se unvisited edges in the context of random cubic graphs. We establish asymptotically correct estimates for the vertex and edge cover times, these being $\approx n\log n$ and $\approx \frac32n\log n$ respectively.

We consider an asynchronous voting process on graphs called discordant voting, which can be described as follows. Initially each vertex holds one of two opinions, red or blue. Neighboring vertices with different opinions interact pairwise along an edge. After an interaction both vertices have the same color. The quantity of interest is the time to reach consensus, i.e., the number of steps needed for all vertices have the same color. We show that for a given initial coloring of the vertices, the expected time to reach consensus depends strongly on the underlying graph and the update rule (i.e., push, pull, oblivious).

We first consider the following problem. We are given a fixed perfect matching $M$ of $[n]$ and we add random edges one at a time until there is a Hamilton cycle containing $M$. We show that with high probability (w.h.p.) the hitting time for this event is the same as that for the first time there are no isolated vertices in the graph induced by the random edges. We then use this result for the following problem. We generate random edges and randomly color them black or white. A path/cycle is said to be zebraic if the colors alternate along the path. We show that w.h.p. the hitting time for a zebraic Hamilton cycle coincides with every vertex meeting at least one edge of each color. We then consider some related problems and (partially) extend our results to multiple colors. We also briefly consider directed versions.

We determine, asymptotically in $n$, the distribution and mean of the weight of a minimum-weight $k$-clique (or any strictly balanced graph $H$) in a complete graph $K_n$ whose edge weights are independent random values drawn from the uniform distribution or other continuous distributions. For the clique, we also provide explicit (nonasymptotic) bounds on the distribution's cumulative distribution function in a form obtained directly from the Stein--Chen method and in a looser but simpler form. The direct form extends to other subgraphs and other edge-weight distributions. We illustrate the clique results for various values of $k$ and $n$. The results may be applied to evaluate whether an observed minimum-weight copy of a graph $H$ in a network provides statistical evidence that the network's edge weights are not independently distributed but have some structure.

Cuckoo Hashing is a hashing scheme invented by Pagh and Rodler [12]. It uses d ≥ 2 distinct hash functions to insert items into the hash table. It has been an open question for some time as to the expected time for Random Walk Insertion to add items. We show that if the number of hash functions d = O(1) is sufficiently large, then the expected insertion time is O(1) per item.

Let $G_{n,p}$ be the standard Erdös--Rényi--Gilbert random graph and let $G_{n,n,p}$ be the random bipartite graph on $n+n$ vertices, where each $e\in [n]^2$ appears as an edge independently with probability $p$. For a graph $G=(V,E)$, suppose that each edge $e\in E$ is given an independent exponential rate 1 cost $X_e$. Let $C(G)$ denote the random variable equal to the length of the minimum cost perfect matching if $G$ contains at least one perfect matching, and let $C(G)=0$ otherwise. Let $\mu(G)=\textbf{E}{C(G)}$. We show that if $np\gg{\log}^{2}n$ and $G=G_{n,n,p}$, then with high probability (w.h.p.) $\mu(G)\approx\frac{{\pi}^2}{6p}$. This generalizes the well-known result for the case $G=K_{n,n}$, where $p=1$. We also show that if $G=G_{n,p}$, then $\mu(G_{n,p}) \approx\frac{{\pi}^2}{12p}$ w.h.p. along with concentration results for both types of random graph.

We consider an asynchronous voting process on graphs which we call discordant voting, and which can be described as follows. Initially each vertex holds one of two opinions, red or blue say. Neighbouring vertices with different opinions interact pairwise. After an interaction both vertices have the same colour. The quantity of interest is T, the time to reach consensus, i.e. the number of interactions needed for all vertices have the same colour. An edge whose endpoint colours differ (i.e. one vertex is coloured red and the other one blue) is said to be discordant. A vertex is discordant if its is incident with a discordant edge. In discordant voting, all interactions are based on discordant edges. Because the voting process is asynchronous there are several ways to update the colours of the interacting vertices. - Push: Pick a random discordant vertex and push its colour to a random discordant neighbour. - Pull: Pick a random discordant vertex and pull the colour of a random discordant neighbour. - Oblivious: Pick a random endpoint of a random discordant edge and push the colour to the other end point. We show that ET, the expected time to reach consensus, depends strongly on the underlying graph and the update rule. For connected graphs on n vertices, and an initial half red, half blue colouring the following hold. For oblivious voting, ET = (n^2)/4 independent of the underlying graph. For the complete graph Kn, the push protocol has ET = Theta(n*log(n)), whereas the pull protocol has ET = Theta(2^n). For the cycle C_n all three protocols have ET = Theta(n^2). For the star graph however, the pull protocol has ET = O(n^2), whereas the push protocol is slower with ET = Theta(n^2*log(n)). The wide variation in ET for the pull protocol is to be contrasted with the well known model of synchronous pull voting, for which ET = O(n) on many classes of expanders.

The classical Beardwood-Halton-Hammersly theorem (1959) asserts the existence of an asymptotic formula of the form constant times square root n for the minimum length of a Traveling Salesperson Tour through n random points in the unit square, and in the decades since it was proved, the existence of such formulas has been shown for other such Euclidean functionals on random points in the unit square as well. Despite more than 50 years of attention, however, it remained unknown whether the minimum length TSP through n random points in the unit square was asymptotically distinct from its natural lower bounds, such as the minimum length spanning tree, the minimum length 2-factor, or, as raised by Goemans and Bertsimas, from its linear programming relaxation. We prove that the TSP on random points in Euclidean space is indeed asymptotically distinct from these and other natural lower bounds, and show that this separation implies that branch-and-bound algorithms based on these natural lower bounds must take nearly exponential time to solve the TSP to optimality, even in average case. This is the first average-case superpolynomial lower bound for these branch-and-bound algorithms.

Given a discrete random walk on a finite graph $G$, the vacant set and vacant net are, respectively, the sets of vertices and edges which remain unvisited by the walk at a given step $t$. Let $\Gamma(t)$ be the subgraph of $G$ induced by the vacant set of the walk at step $t$. Similarly, let $\widehat \Gamma(t)$ be the subgraph of $G$ induced by the edges of the vacant net. For random $r$-regular graphs $G_r$, it was previously established that for a simple random walk the graph $\Gamma(t)$ of the vacant set undergoes a phase transition in the sense of the phase transition on Erdös--Renyi graphs $G_{n,p}$. Thus, for $r \ge 3$ there is an explicit value $t^*=t^*(r)$ of the walk such that for $t\leq (1-\epsilon)t^*$, $\Gamma(t)$ has a unique giant component, plus components of size $O(\log n)$, whereas for $t\geq (1+\epsilon)t^*$ all the components of $\Gamma(t)$ are of size $O(\log n)$. In this paper we establish the threshold value $\widehat t$ for a phase transition in the graph $\widehat \Gamma(t)$ of the vacant net of a simple random walk on a random $r$-regular graph. We obtain the corresponding threshold results for the vacant set and vacant net of two modified random walks. These are a nonbacktracking random walk and, for $r$ even, a random walk which chooses unvisited edges whenever available. This allows a direct comparison of thresholds between simple and modified walks on random $r$-regular graphs. The main findings are the following: As $r$ increases, the threshold for the vacant set converges to $n \log r$ in all three walks. For the vacant net, the threshold converges to $rn/2 \; \log n$ for both the simple random walk and the nonbacktracking random walk. When $r\ge 4$ is even, the threshold for the vacant net of the unvisited edge process converges to $rn/2$, which is also the vertex cover time of the process.

An edge colored graph $G$ is rainbow edge connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection of a connected graph $G$, denoted by $rc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow connected. In this work we study the rainbow connection of the random $r$-regular graph $G=G(n,r)$ of order $n$, where $r\ge 4$ is a constant. We prove that with probability tending to one as $n$ goes to infinity the rainbow connection of $G$ satisfies $rc(G)=O(\log n)$, which is best possible up to a hidden constant.

We introduce and analyze the Walker-Breaker game, a variant of Maker-Breaker games where Maker is constrained to choose edges of a walk or path in a given graph $G$, with the goal of visiting as many vertices of the underlying graph as possible.

Let $\mathbf{\Phi}$ be a uniformly distributed random $k$-SAT formula with $n$ variables and $m$ clauses. We prove that the \tt Walksat algorithm from Papadimitriou [On selecting a satisfying truth assignment, in Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Soc., Los Alamitos, CA, 1991, pp. 163--169] and Schöning [A probabilistic algorithm for $k$-SAT and constraint satisfaction problems, in Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Soc., Los Alamitos, CA, 1999, pp. 410--414] finds a satisfying assignment of $\mathbf{\Phi}$ in polynomial time with high probability if $m/n\leq\rho\cdot2^k/k$ for a certain constant $\rho>0$. This is an improvement by a factor of $\Theta(k)$ over the best previous analysis of \tt Walksat from Coja-Oghlan et al. [On smoothed $k$-CNF formulas and the Walksat algorithm, in Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM, New York, SIAM, Philadelphia, 2009, pp. 451--460].

Motivated by the problem of routing reliably and scalably in a graph, we introduce the notion of a splicer, the union of a small number of spanning trees of a graph. We prove that for any bounded-degree $n$-vertex graph, the union of two uniformly random spanning trees approximates the expansion of the graph to within a factor of $O(\log n)$. For the complete graph, we prove that the union of two uniformly random spanning trees is an expander with high probability. For the random graph $G_{n,p}$, for $p = \Omega(\log{n}/n)$, we give a randomized algorithm for constructing two spanning trees whose union is an expander. A closely related construction, which we call a selector, has similar properties. A random selector of a graph is obtained by starting with any spanning tree of the graph and adding a small number of random edges at each vertex.

Network science has emerged over the last years as an interdisciplinary area spanning traditional domains including mathematics, computer science, sociology, biology and economics. Since complexity in social, biological and economical systems, and more generally in complex systems, arises through pairwise interactions there exists a surging interest in understanding networks.

This issue of SICOMP contains eight selected papers from the Forty-Second Annual ACM Symposium on Theory of Computing (STOC 2010), held June 6--8, 2010, in Cambridge, Massachusetts. The STOC proceedings contained 78 papers, which the program committee selected from 279 submissions. The program committee consisted of Timothy Chan, Ken Clarkson, Constantinos Daskalakis, Irit Dinur, Faith Ellen, Alan Frieze, Parikshit Gopalan, Piotr Indyk, Valentine Kabanets, Yael Tauman Kalai, Howard Karloff, Robert Kleinberg, Assaf Naor, Noam Nisan, Chris Peikert, Jaikumar Radhakrishnan, Oded Regev, Alexander Russell, Leonard Schulman (chair), Aravind Srinivasan, Santosh Vempala, and Andrew Yao. Eight of the STOC papers appear in this special section, each expanded and subjected to the standard thorough reviewing process of the journal. They cover a diverse collection of topics: In “Improving Exhaustive Search Implies Superpolynomial Lower Bounds," R. Ryan Williams shows that there are natural problems in NP and BPP for which algorithms that improve over the naïve deterministic simulation even quite slightly, imply lower bounds such as NEXP $\not\in$ P/poly and LOGSPACE $\neq$ NP. Williams also proves certain unconditional time-space lower bounds for improving on exhaustive search; the length of the witness-string in some standard verification protocol is a key parameter here. In “An Effective Dichotomy for the Counting Constraint Satisfaction Problem," Martin Dyer and David Richerby consider the counting constraint satisfaction problem (\#CSP). This problem asks how many ways there are to satisfy a system of constraints on a set of variables, where a constraint is a relation chosen from a fixed finite set. This class is shown to have a decidable dichotomy, depending on the form of the relations. The dichotomy is that each problem in the class either is in FP or is \#P-complete, with no intermediate cases. In “Pseudorandom Generators for Polynomial Threshold Functions," Raghu Meka and David Zuckerman develop improved (and in many cases the first nontrivial) pseudorandom generators for low-degree polynomial threshold functions; related explicit constructions are also developed. A key ingredient is the use of invariance principles to construct pseudorandom generators. In “Local List-Decoding and Testing of Random Linear Codes from High Error," Swastik Kopparty and Shubhangi Saraf give efficient local list-decoding and testing algorithms for “sparse" random linear codes, and subexponential time algorithms for list-decoding random linear codes, which tolerate error rates approaching $1/2$. In “How to Compress Interactive Communication," Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao attack the important direct sum problem in communication complexity: is the complexity of evaluating $n$ copies of a function ever significantly less than $n$ times the complexity of evaluating it once? By defining a new notion of information cost for protocols --- the so-called internal information cost --- and providing new protocol compression schemes, they prove that computing $n$ copies of any function requires communicating at least $\sqrt{n}$ times as many bits as computing one copy of the function. In “A Deterministic Single Exponential Time Algorithm for Most Lattice Problems based on Voronoi Cell Computations," Daniele Micciancio and Panagiotis Voulgaris provide the first $\exp(O(n))$-time algorithms for the closest vector problem (CVP) and shortest independent vectors problem (SIVP); their algorithm is, moreover, deterministic. Likewise they provide a deterministic algorithm for the shortest vector problem (SVP), whose $\exp(O(n))$ runtime is an improvement over the best known bounds for randomized algorithms. In “Perfect Matchings in $O(n \log n)$ Time in Regular Bipartite Graphs," Ashish Goel, Michael Kapralov, and Sanjeev Khanna provide a randomized algorithm that finds a perfect matching in a $d$-regular $n$-node bipartite graph in time $O(n \log n)$, notably, within time that may be sublinear in the input size and is independent of the degree. In “Efficiency Improvements in Constructing Pseudorandom Generators from One-Way Functions," Iftach Haitner, Omer Reingold, and Salil Vadhan give a new construction of pseudorandom generators from one-way functions that both simplifies and tightens the acclaimed original construction of Hastad, Impagliazzo, Levin, and Luby. We thank the authors, the STOC program committee, the STOC external reviewers, and the journal referees for all their work to make this special issue possible.

Given a graph $G$ and an integer $k$, two players take turns coloring the vertices of $G$ one by one using $k$ colors so that neighboring vertices get different colors. The first player wins iff at the end of the game all the vertices of $G$ are colored. The game chromatic number $\chi_g(G)$ is the minimum $k$ for which the first player has a winning strategy. The paper [T. Bohman, A. M. Frieze, and B. Sudakov, Random Structures Algorithms, 32 (2008), pp. 223--235] began the analysis of the asymptotic behavior of this parameter for a random graph $G_{n,p}$. This paper provides some further analysis for graphs with constant average degree, i.e., $np=O(1)$, and for random regular graphs. We show that with high probability (w.h.p.) $c_1\chi(G_{n,p})\leq \chi_g(G_{n,p})\leq c_2\chi(G_{n,p})$ for some absolute constants $1

We say that a k-uniform hypergraph C is a Hamilton cycle of type $\ell$, for some $1\leq\ell\leq k$, if there exists a cyclic ordering of the vertices of C such that every edge consists of k consecutive vertices, and for every pair of consecutive edges $E_{i-1},E_i$ in C (in the natural ordering of the edges) we have $|E_{i-1}\setminus E_i|=\ell$. We define a class of $(\epsilon,p)$-regular hypergraphs, that includes random hypergraphs, for which we can prove the existence of a decomposition of almost all edges into type $\ell$ Hamilton cycles, where $\ell

We consider random walks on two classes of random graphs and explore the likely structure of the the set of unvisited vertices (or vacant set). Let Γ(t) be the subgraph induced by the vacant set. We show that for random graphs Gn,p above the connectivity threshold, and for random regular graphs Gr, for constant r ≥ 3, there is a phase transition in the sense of the well-known Erdős-Renyi phase transition. Thus for t ≤ (1 − ∊)t* we have a unique giant plus components of size O(log n) and for t ≥ (1 + ∊)t* we have only components of size O(log n). In the case of Gr we describe the likely degree sequence and structure of the small (O(log n)) size components.

Consider a 3-uniform hypergraph H with n vertices. A tight Hamilton cycle C ⊂ H is a collection of n edges for which there is an ordering of the vertices v1, …, vn where every triple of consecutive vertices {vi, vi+1, vi+2} is an edge of C (indices considered modulo n). We develop new techniques which show that under certain natural pseudo-random conditions, almost all edges of H can be covered by edge-disjoint tight Hamilton cycles, for n divisible by 4. Consequently, random 3-uniform hypergraphs can be almost completely packed with tight Hamilton cycles whp, for n divisible by 4 and p not too small. Along the way, we develop a similar result for packing Hamilton cycles in pseudo-random digraphs with even numbers of vertices.

In this paper, we provide a polylogarithmic bound that holds with high probability on the insertion time for cuckoo hashing under the random-walk insertion method. Cuckoo hashing provides a useful methodology for building practical, high-performance hash tables. The essential idea of cuckoo hashing is to combine the power of schemes that allow multiple hash locations for an item with the power to dynamically change the location of an item among its possible locations. Previous work on the case where the number of choices is larger than two has analyzed breadth-first search, which is both inefficient in practice and currently has only a polynomial upper bound on the insertion time that holds with high probability. On the other hand, it does have expected constant amortized insertion time. Here we significantly advance the state of the art by proving a polylogarithmic bound that holds with high probability on the more efficient random-walk method, where items repeatedly kick out random blocking items until a free location for an item is found.

We present a linear expected time algorithm for finding maximum cardinality matchings in sparse random graphs. This is optimal and improves on previous results by a logarithmic factor.

We study a problem motivated by a question related to quantum error-correcting codes. Combinatorially, it involves the graph parameter $f(G)=\min\{|A|+|\{x\in V\setminus A:d_A(x)$ is $\text{odd}\}|:A\neq\emptyset\}$, where V is the vertex set of G and $d_A(x)$ is the number of neighbors of x in A. We give asymptotically tight estimates of f for the random graph $G_{n,p}$ when p is constant. Also, if $f(n)=\max\{f(G):\,|V(G)|=n\}$, then we show that $f(n)\leq(0.382+o(1))n$.

Let ${\bf A}$ be a $0/1$ matrix of size $m\times n$, and let p be the density of ${\bf A}$ (i.e., the number of ones divided by $m\cdot n$). We show that ${\bf A}$ can be approximated in the cut norm within $\varepsilon\cdot mnp$ by a sum of cut matrices (of rank 1), where the number of summands is independent of the size $m\cdot n$ of ${\bf A}$, provided that ${\bf A}$ satisfies a certain boundedness condition. This decomposition can be computed in polynomial time. This result extends the work of Frieze and Kannan [Combinatorica, 19 (1999), pp. 175–220] to sparse matrices. As an application, we obtain efficient $1-\varepsilon$ approximation algorithms for “bounded” instances of MAX CSP problems.

If $m\geq2$ is constant and $0\leq r\leq\varepsilon\log\log n$ for a small positive constant $\varepsilon$, then whp a random walk with look-ahead r on a scale-free graph $G=G_{(m,n)}$ has cover time $C_G(r)\sim(2/(m^{r-1}(m-1)))\;n\log n$.

Let $\mathbf{d}=d_1\leq d_2\leq\dots\leq d_n$ be a nondecreasing sequence of n positive integers whose sum is even. Let $\mathcal{G}_{n,\mathbf{d}}$ denote the set of graphs with vertex set $[n]=\{1,2,\dots,n\}$ in which the degree of vertex i is $d_i$. Let $G_{n,\mathbf{d}}$ be chosen uniformly at random from $\mathcal{G}_{n,\mathbf{d}}$. It will be apparent from section 4.3 that all of the sequences we are considering will be graphic. We give a condition on $\mathbf{d}$ under which we can show that whp $\mathcal{G}_{n,\mathbf{d}}$ is Hamiltonian. This condition is satisfied by graphs with exponential tails as well those with power law tails.

Let A be a 0/1 matrix of size m×n, and let p be the density of A (i.e., the number of ones divided by m · n). We show that A can be approximated in the cut norm within ∊ · mnp by a sum of cut matrices (of rank 1), where the number of summands is independent of the size m · n of A, provided that A satisfies a certain boundedness condition. The decomposition can be computed in polynomial time. This result extends the work of Frieze and Kannan (Combinatorica 1999) to sparse matrices. As an application, we obtain efficient 1 – ∊ approximation algorithms for “bounded” instances of Max CSP problems.

In this paper we study the model of ∊-smoothed k-CNF formulas. Starting from an arbitrary instance F with n variables and m = dn clauses, apply the ∊-smoothing operation of flipping the polarity of every literal in every clause independently at random with probability ∊. Keeping ∊ and k fixed, and letting the density d = m/n grow, it is rather easy to see that for d ≥ ∊−-kln 2, F becomes whp unsatisfiable after smoothing. We show that a lower density that behaves roughly like ∊−-k+1 suffices for this purpose. We also show that our bound on d is nearly best possible in the sense that there are k-CNF formulas F of slightly lower density that whp remain satisfiable after smoothing. One consequence of our proof is a new lower bound of Ω(2k/k2) on the density up to which Walksat solves random k-CNFs in polynomial time whp. We are not aware of any previous rigorous analysis showing that Walksat is successful at densities that are increasing as a function of k.

We study the cover time of random geometric graphs. Let I(d) = [0, 1]d denote the unit torus in d dimensions. Let D(x, r) denote the ball (disc) of radius r. Let ϒd be the volume of the unit ball D(0, 1) in d dimensions. A random geometric graph G = G(d, r, n) in d dimensions is defined as follows: Sample n points V independently and uniformly at random from I(d). For each point x draw a ball D(x, r) of radius r about x. The vertex set V(G) = V and the edge set E (G) = {{v, w} : w ≠ v, w ∊ D(v, r)}. Let G(d, r, n), d ≥ 3 be a random geometric graph. Let c > 1 be constant, and let r = (c log n/(ϒdn))1/d. Then whp

In an Achlioptas process two random pairs of $\{1,\dots,n\}$ arrive in each round and the player has to choose one of them. We study the very restrictive version where a player's decisions cannot depend on the previous history and only one vertex from the two random edges is revealed. We prove that the player can create a giant component in $(2\sqrt{5}-4+o(1))n=(0.4721\ldots+o(1))n$ rounds and that this is the best possible. On the other hand, if the player wants to delay the appearance of a giant, then the optimal bound is $(1/2+o(1))n$, the same as in the Erdős–Rényi model.

We study properties of multiple random walks on a graph under various assumptions of interaction between the particles. To give precise results, we make the analysis for random regular graphs. The cover time of a random walk on a random r-regular graph was studied in [C. Cooper and A. Frieze, SIAM J. Discrete Math., 18 (2005), pp. 728–740], where it was shown with high probability (whp) that for $r\geq3$ the cover time is asymptotic to $\theta_r n\ln n$, where $\theta_r=(r-1)/(r-2)$. In this paper we prove the following (whp) results, arising from the study of multiple random walks on a random regular graph G. For k independent walks on G, the cover time $C_G(k)$ is asymptotic to $C_G/k$, where $C_G$ is the cover time of a single walk. For most starting positions, the expected number of steps before any of the walks meet is $\theta_r n/\binom{k}{2}$. If the walks can communicate when meeting at a vertex, we show that, for most starting positions, the expected time for k walks to broadcast a single piece of information to each other is asymptotic to $\frac{2\ln k}{k}\theta_r n$ as $k,n\rightarrow\infty$. We also establish properties of walks where there are two types of particles, predator and prey, or where particles interact when they meet at a vertex by coalescing or by annihilating each other. For example, the expected extinction time of k explosive particles (k even) tends to $(2\ln2)\theta_r n$ as $k\rightarrow\infty$. The case of n coalescing particles, where one particle is initially located at each vertex, corresponds to a voter model defined as follows: Initially each vertex has a distinct opinion, and at each step each vertex changes its opinion to that of a random neighbor. The expected time for a unique opinion to emerge is the same as the expected time for all the particles to coalesce, which is asymptotic to $2\theta_r n$. Combining results from the predator-prey and multiple random walk models allows us to compare expected detection times of all prey in the following scenarios: Both the predator and the prey move randomly, the prey moves randomly and the predators stay fixed, and the predators move randomly and the prey stays fixed. In all cases, with k predators and $\ell$ prey the expected detection time is $\theta_r H_{\ell}n/k$, where $H_{\ell}$ is the $\ell$th harmonic number.

We study the problem of finding a large planted clique in the random graph $G_{n,1/2}$. We reduce the problem to that of maximising a three dimensional tensor over the unit ball in $n$ dimensions. This latter problem has not been well studied and so we hope that this reduction will eventually lead to an improved solution to the planted clique problem.

We propose the following model of a random graph on n vertices. Let F be a distribution in R+n(n-1)/2 with a coordinate for every pair ij with 1 ≤ i,j ≤ n. Then GF,p is the distribution on graphs with n vertices obtained by picking a random point X from F and defining a graph on n vertices whose edges are pairs ij for which Xij ≤ p. The standard Erdos-Renyi model is the special case when F is uniform on the 0-1 unit cube. We determine basic properties such as the connectivity threshold for quite general distributions. We also consider cases where the Xij are the edge weights in some random instance of a combinatorial optimization problem. By choosing suitable distributions, we can capture random graphs with interesting properties such as triangle-free random graphs and weighted random graphs with bounded total weight.

An n-lift of a digraph K is a digraph with a vertex set $V(K)\times [n]$, and for each directed edge $(i,j)\in E(K)$ there is a perfect matching between fibers $\{i\}\times [n]$ and $\{j\}\times [n]$, with edges directed from fiber i to fiber j. If these matchings are chosen independently and uniformly at random, then we say that we have a random n-lift. We show that if h is sufficiently large, then a random n-lift of the complete digraph $\DK_h$ is a Hamiltonian .

We consider the gap between the cost of an optimal assignment in a complete bipartite graph with random edge weights, and the cost of an optimal traveling salesman tour in a complete directed graph with the same edge weights. Using an improved “patching” heuristic, we show that with high probability the gap is $O((\ln n)^2/n)$, and that its expectation is $\Omega(1/n)$. One of the underpinnings of this result is that the largest edge weight in an optimal assignment has expectation $\Theta(\ln n / n)$. A consequence of the small assignment–TSP gap is an $e^{\tilde{O}(\sqrt{n})}$‐time algorithm which, with high probability, exactly solves a random asymmetric traveling salesman instance. In addition to the assignment–TSP gap, we also consider the expected gap between the optimal and second‐best assignments; it is at least $\Omega(1/n^2)$ and at most $O(\ln n/n^2)$.

In this paper we deal with codes identifying sets of vertices in random graphs, that is l-identifying codes. These codes enable us to detect sets of faulty processors in a multiprocessor system, assuming that the maximum number of faulty processors is bounded by a fixed constant l. The l-identifying codes or simply identifying codes are of special interest. For random graphs we use the model G(n,p), in which each one of the (/sub 2//sup n/) possible edges exists with probability p. We give upper and lower bounds on the minimum cardinality of an l-identifying code in a random graph, as well as threshold functions for the property of admitting such a code. We derive existence results from probabilistic constructions. A connection between identifying codes and superimposed codes is also established.

In combinatorial optimization, a popular approach toNP-hard problems is the design of approximation algorithms. These algorithms typically run in polynomial time and are guaranteed to produce a solution which is within a known multiplicative factor of optimal. Unfortunately, the known factor is often known to be large in pathological instances. Conventional wisdom holds that, in practice, approximation algorithms will produce solutions closer to optimal than their proven guarantees. In this paper, we use the rigorous-analysis-of-heuristics framework to investigate this conventional wisdom.We analyze the performance of 3 related approximation algorithms for the uncapacitated facility location problem (from [Jain, Mahdian, Markakis, Saberi, Vazirani, 2003] and [Mahdian, Ye, Zhang, 2002]) when each is applied to an instances created by placing n points uniformly at random in the unit square. We find that, with high probability, these 3 algorithms do not find asymptotically optimal solutions, and, also with high probability, a simple plane partitioning heuristic does find an asymptotically optimal solution.

Let $r \ge 3$ be constant, and let ${\cal G}_{r}$ denote the set of r-regular graphs with vertex set V = {1,2,...,n}. Let G be chosen randomly from ${\cal G}_{r}$. We prove that with high probability (\whp) the cover time of a random walk on G is asymptotic to $\frac{r-1}{r-2}\;n\log n$.

The strong chromatic index of a graph G, denoted by $\chi_s(G)$, is the minimum number of colors needed to color its edges so that each color class is an induced matching. In this paper we analyze the asymptotic behavior of this parameter in a random graph $G(n,p)$, for two regions of the edge probability $p=p(n)$. For the dense case, where p is a constant, $0 < p < 1$, we prove that with high probability $\chi_s(G)\le (1+o(1))\frac{3}{4}\frac{n^2p}{\log_bn}$, where $b=1/(1-p)$. This improves upon a result of Czygrinow and Nagle [{\it Discrete Math.}, 281 (2004), pp. 129--136]. For the sparse case, where $np< \frac{1}{100}\sqrt{\log n/\log\log n}$, we show that with high probability $\chi_s(G)=\Delta_1(G)$, where $\Delta_1(G)=\max\{d(u)+d(v)-1:\ (u,v)\in E(G)\}$. This improves a result of Palka [{\it Australas. J. Combin.}, 18 (1998), pp. 219--226].

We consider the problem of approximating a given m × n matrix A by another matrix of specified rank k , which is smaller than m and n . The Singular Value Decomposition (SVD) can be used to find the "best" such approximation. However, it takes time polynomial in m, n which is prohibitive for some modern applications. In this article, we develop an algorithm that is qualitatively faster, provided we may sample the entries of the matrix in accordance with a natural probability distribution. In many applications, such sampling can be done efficiently. Our main result is a randomized algorithm to find the description of a matrix D * of rank at most k so that holds with probability at least 1 − δ (where |·| F is the Frobenius norm). The algorithm takes time polynomial in k ,1/ϵ, log(1/δ) only and is independent of m and n . In particular, this implies that in constant time, it can be determined if a given matrix of arbitrary size has a good low-rank approximation.

Given a digraph D=(V,A) and a set of $\kappa$ pairs of vertices in V, we are interested in finding, for each pair (x i , y i ), a directed path connecting x i to y i such that the set of $\kappa$ paths so found is arc-disjoint. For arbitrary graphs the problem is ${\cal NP}$-complete, even for $\kappa=2$. We present a polynomial time randomized algorithm for finding arc-disjoint paths in an r-regular expander digraph D. We show that if D has sufficiently strong expansion properties and the degree r is sufficiently large, then all sets of $\kappa=\Omega(n/\log n)$ pairs of vertices can be joined. This is within a constant factor of best possible.

Let the edges of the complete graph K/sub n/ be assigned independent uniform [0,1] random edge weights. Let Z/sub TSP/ and Z/sub 2FAC/ be the weights of the minimum length travelling salesman tour and minimum weight 2-factor respectively. We show that whp/sup 1/ |Z/sub TSP/-Z/sub 2FAC/|=(1). The proof is via the analysis of a polynomial time algorithm that finds a tour only a little longer than Z/sub 2FAC/.

Introduction We consider a simple model of an agent (which we call a spider) moving between the nodes of a randomly growing web graph. It is presumed that the agent examines the page content of the node for some specific topic. In our model the spider makes a random walk on the existing set of vertices. We compare the success of the spider on web graphs of two distinct types. For a random graph web graph model, in which new vertices join edges to existing vertices uniformly at random, the expected proportion of unvisited vertices tends to 0.57. For the comparable copy-based web graph model, in which new vertices join edges to existing vertices proportional to vertex degree, the expected proportion of unvisited vertices tends to 0.59. A web graph is a sparse connected graph designed to capture some properties of the www. Studies of the graph structure of the www were made by [4] and [7] among others. There are many models of web graphs designed to capture the structure of the www foun

We prove two results concerning approximate counting of independent sets in graphs with constant maximum degree $\Delta$. The first implies that the Markov chain Monte Carlo technique is likely to fail if $\Delta \geq 6$. The second shows that no fully polynomial randomized approximation scheme can exist for $\Delta \geq 25$, unless $\mathrm{RP}=\mathrm{NP}$.

Given a digraph D=(V, A) and a set of /spl kappa/ pairs of vertices in V, we are interested in finding for each pair (x/sub i/, y/sub i/), a directed path connecting x/sub i/ to y/sub i/, such that the set of /spl kappa/ paths so found is arc-disjoint. For arbitrary graphs, the problem is /spl Nscr//spl Pscr/-complete, even for /spl kappa/=2. We present a polynomial time randomized algorithm for finding arc-disjoint paths in an r-regular expander digraph D. We show that if D has sufficiently strong expansion properties and r is sufficiently large, then all sets of /spl kappa/=/spl Omega/(n/log n) pairs of vertices can be joined. This is within a constant factor of best possible.

We consider the problem of generating a random q-colouring of a graph G=(V, E). We consider the simple Glauber Dynamics chain. We show that if the maximum degree /spl Delta/>c/sub l/ ln n and the girth g>c/sub 2/ ln ln n (n=|V|), then this chain mixes rapidly provided C/sub 1/, C/sub 2/ are sufficiently large, q/A>/spl beta/, where /spl beta//spl ap/1.763 is the root of /spl beta/=e/sup 1//spl beta//. For this class of graphs, this beats the 11/spl Delta//6 bound of E. Vigoda (1999) for general graphs. We extend the result to random graphs.

Sequencing by hybridization (SBH) is a method for reconstructing a sequence over a small finite alphabet from a collection of probes (substrings). Substring queries can be arranged on an array (SBH chip) and then a combinatorial method is used to construct the sequence from its collection of probes. Technological constraints limit the number of substring queries that can be placed on a single SBH chip. We develop an idea of Margaritis and Skiena and propose an algorithm that uses a series of small SBH chips to sequence long strings while the number of probes used matches the information theoretical lower bound up to a constant factor.

We prove a sufficient condition for the stability of dynamic packet routing algorithms. Our approach reduces the problem of steady state analysis to the easier and better understood question of static routing. We show that certain high probability and worst case bounds on the quasi-static (finite past) performance of a routing algorithm imply bounds on the performance of the dynamic version of that algorithm. Our technique is particularly useful in analyzing routing on networks with bounded buffers where complicated dependices make standard queuing techniques inapplicable. We present several applications of our approach. In all cases we start from a known static algorithm, and modify it to fit our framework. In particular we give the first dynamic algorithms for routing on a butterfly or two-dimensional mesh with bounded buffers. Both the injection rate for which the algorithm is stable, and the expected time a packet spends in the system are optimal up to constant factors. Our approach is also applicable to the recently introduced adversarial input model.

Given a graph G=(V,E)and a set of $\kappa$ pairs of vertices in V, we are interested in finding, for each pair (a i , b i ), a path connecting a i to b i such that the set of $\kappa$ paths so found is edge-disjoint. For arbitrary graphs the problem is ${\cal NP}$-complete, although it is in ${\cal P}$ if $\kappa$ is fixed. We present a polynomial time randomized algorithm for finding edge-disjoint paths in an r-regular expander graph G. We show that if G has sufficiently strong expansion properties and r is sufficiently large, then all sets of $\kappa=\Omega(n/\log n)$ pairs of vertices can be joined. This is within a constant factorof best possible.

Studies two widely used algorithms, Glauber dynamics and the Swendsen-Wang (1987) algorithm, on rectangular subsets of the hypercubic lattice Z/sup d/. We prove that, under certain circumstances, the mixing time in a box of side length L with periodic boundary conditions can be exponential in L/sup d-1/. In other words, under these circumstances, the mixing in these widely used algorithms is not rapid; instead it is torpid. The models we study are the independent set model and the q-state Potts model. For both models, we prove that Glauber dynamics is torpid in the region with phase coexistence. For the Potts model, we prove that the Swendsen-Wang mixing is torpid at the phase transition point.

We prove two results concerning approximate counting of independent sets in graphs with constant maximum degree /spl Delta/. The first result implies that the Monte-Carlo Markov chain technique is likely to fail if /spl Delta//spl ges/6. The second shows that no fully polynomial randomized approximation scheme can exist for /spl Delta//spl ges/25, unless P=NP under randomized reductions.

Sequencing by hybridizationis a novel DNA sequencing technique in which an array (SBH chip) of short sequences of nucleotides (probes) is brought in contact with a solution of (replicas of) the target DNA sequence.A biochemical method determines the subset of probes that bind to the target sequence (the spectrum of the sequence), and a combinatorial method is used to reconstruct the DNA sequence from the spectrum.Since technology limits the number of probes on the SBH chip, a challenging combinatorial question is the design of a smallest set of probes that can sequence an arbitrary DNA string of a given length.We show in this work that the use of universal bases (bases that bind to any nucleotide [LB94]) can drastically improve the performance of the SBH process.We present a novel probe design with performance that asymptotically approaches the information-theoretical bound up to a constant factor, and, for any number of probes, is significantly better than previously analyzed probe patterns.Furthermore, the sequencing algorithm we use is substantially simpler than the Eulerian path method used in previous work.

We prove that the sum of two random trees possesses with high probability a perfect matching and the sum of five random trees possesses with high probability a Hamilton cycle.

In several applications, the data consists of an m/spl times/n matrix A and it is of interest to find an approximation D of a specified rank k to A where, k is much smaller than m and n. Traditional methods like the Singular Value Decomposition (SVD) help us find the "best" such approximation. However, these methods take time polynomial in m, n which is often too prohibitive. In this paper, we develop an algorithm which is qualitatively faster provided we may sample the entries of the matrix according to a natural probability distribution. Indeed, in the applications such sampling is possible. Our main result is that we can find the description of a matrix D* of rank at most k so that /spl par/A-D*/spl par//sub F//spl les/min/D,rank(D)/spl les/k/spl par/A-D/spl par//sub F/+/spl epsiv//spl par/A/spl par//sub F/ holds with probability at least 1-/spl delta/. (For any matrix M, /spl par/M/spl par//sub F//sup 2/ denotes the sum of the squares of all the entries of M.) The algorithm takes time polynomial in k, 1//spl epsiv/, log(1//spl delta/) only, independent of m, n.

We define and study the notion of min-wise independent families of permutations.We say that F ⊆ S n is min-wise independent if for any set X ⊆ [n] and any x ∈ X, when π is chosen at random in F we have Pr min{π(X)} = π(x) = 1 |X| .

Given a graph G=(V,E) with n vertices, m edges, and a family of $\kappa$ pairs of vertices in V, we are interested in finding for each pair (a i , b i ) a path connecting a i to b i such that the set of $\kappa$ paths so found is edge disjoint. (For arbitrary graphs the problem is ${\cal NP}$-complete, although it is in ${\cal P}$ if $\kappa$ is fixed.) We present a polynomial time randomized algorithm for finding the optimal number of edge disjoint paths (up to constant factors) in the random graph G n,m for all edge densities above the connectivity threshold. (The graph is chosen first; then an adversary chooses the pairs of endpoints.) Our results give the first tight bounds for the edge-disjoint paths problem for any nontrivial class of graphs.

We describe fully polynomial randomized approximation schemes for the problems of determining the number of Hamilton paths and cycles in an n-vertex graph with minimum degree $(\frac{1}{2}+\a)n$, for any fixed a > 0. We show that the exact counting problems are #P-complete. We also describe fully polynomial randomized approximation schemes for counting paths and cycles of all sizes in such graphs.

This paper addresses the problem of virtual circuit switching in bounded degree expander graphs.We study the static and dynamic versions of this problem.Our solutions are baaed on the rapidly mixing properties of random walks on expander graphs.In the static version of the problem an algorithm is required to route a path between each of K pairs of vertices so that no edge is used by more than g paths.A natural approach to this problem is through a multicommodity flow reduction.However, we show that the random walk approach leads to significantly stronger results than those recently obtained by Leighton and Rao [10] using the multi-commodity flow setup.In the dynamic version of the problem connection requests are continuously injected into the network, Once a connection is established it utilizes a path (a virtual circuit) for a certain time until the communication terminates and the pat h is deleted.Again each edge in the network should not be used by more than g paths at once.The dynamic version is a better model for the practical use of communication networks.Our random walk approach gives a simple and fully distributed solution for this problem.We show that if the injection to the network and the duration of connections are both controlled by Poisson processes then our algorithm achieves

We present a randomized procedure for rounding fractional perfect matchings to (integral) matchings. If the original fractional matching satisfies any linear inequality, then with high probability, the new matching satisfies that linear inequality in an approximate sense. This extends the well-known LP rounding procedure of Raghavan and Thompson (1987), which is usually used to round fractional solutions of linear programs. It also solves an open problem of Luby and Nisan (1993) ("Design an NC procedure for converting near-optimum fractional matchings to near-optimum matchings.") We use the rounding procedure to design n/sup 0(logn//spl epsiv/(2)/) time algorithms for the following: (i) an additive approximation to the 0-1 Quadratic Assignment problem (QAP); (ii) a (1+E)-approximation for "dense" instances of many well-known NP-hard problems, including (an optimization formulation of) GRAPH-ISOMORPHISM, MIN-CUT-LINEAR-ARRANGEMENT, MAX-ACYCLIC-SUBGRAPH, MIN-LINEAR-ARRANGEMENT, and BETWEENNESS. (A "dense" graph is one in which the number of edges is /spl Omega/(n/sup 2/); denseness for the other problems is defined in an analogous way).

The authors consider the problem of learning a linear threshold function (a halfspace in n dimensions, also called a "perceptron"). Methods for solving this problem generally fall into two categories. In the absence of noise, this problem can be formulated as a linear program and solved in polynomial time with the ellipsoid algorithm (or interior point methods). On the other hand, simple greedy algorithms such as the perceptron algorithm seem to work well in practice and can be made noise tolerant; but, their running time depends on a separation parameter (which quantifies the amount of "wiggle room" available) and can be exponential in the description length of the input. They show how simple greedy methods can be used to find weak hypotheses (hypotheses that classify noticeably more than half of the examples) in polynomial time, without dependence on any separation parameter. This results in a polynomial-time algorithm for learning linear threshold functions in the PAC model in the presence of random classification noise. The algorithm is based on a new method for removing outliers in data. Specifically, for any set S of points in R/sup n/, each given to b bits of precision, they show that one can remove only a small fraction of S so that in the remaining set T, for every vector v, max/sub x/spl epsiv/T/(v/spl middot/x)/sup 2//spl les/poly(n,b)|T|/sup -1//spl Sigma//sub x/spl epsiv/T/(v/spl middot/x)/sup 2/. After removing these outliers, they are able to show that a modified version of the perceptron learning algorithm works in polynomial time, even in the presence of random classification noise.

We prove a sufficient condition for the stability of dynamic packet routing algorithms. Our approach reduces the problem of steady state analysis to the easier and better understood question of static routing. We show that certain high probability and worst case bounds on the quasistatic (finite past) performance of a routing algorithm imply bounds on the performance of the dynamic version of that algorithm. Our technique is particularly useful in analyzing routing on networks with bounded buffers where complicated dependencies make standard queuing techniques inapplicable. We present several applications of our approach. In all cases we start from a known static algorithm, and modify it to fit our framework. In particular we give the first dynamic algorithm for routing on a butterfly with bounded buffers. Both the injection rate for which the algorithm is stable, and the expected time a packet spends in the system are optimal up to constant factors. Our approach is also applicable to the recently introduced adversarial input model.

We present a polynomial time algorithm to learn (in Valiant's PAC model) an arbitrarily oriented cube in n-space, given uniformly distributed sample points from it. In fact, we solve the more general problem of learning, in polynomial time, a linear (affine) transformation of a product distribution.

There are two main contributions of the present paper. In the first, we use the constructive version of the Regularity Lemma to give directly simple polynomial time approximation schemes for several graph "subdivision" problems in dense graphs including the Max Cut problem, the Graph Bisection problem, the Min l-way cut problem and Graph Separator problem. Arora, Karger and Karpinski (1992) gave the first PTASs for these problems whose running time is O(n/sup o(1/e2)/). Our PTASs have running time where the exponent of n is a constant independent of e. The central point here is that the Regularity Lemma provides an explanation of why these Max-SNP hard problems turn out to be easy in dense graphs. We also give a simple PTAS for dense versions of a special case of the Quadratic Assignment Problem (QAP).

We consider the probabilistic relationship between the value of a random asymmetric traveling salesman problem $\textit{ATSP}(M)$ and the value of its assignment relaxation $\textit{AP}(M)$. We assume here that the costs are given by an $n \times n$ matrix M whose entries are independently and identically distributed. We focus on the relationship between $Pr(\textit{ATSP}(M) = \textit{AP}(M))$ and the probability $p_{n}$ that any particular entry is zero. If $np_{n} \rightarrow \infty $ with n then we prove that $\textit{ATSP}(M) = \textit{AP}(M)$ with probability 1-o(1). This is shown to be best possible in the sense that if $np (n) \rightarrow c,\, c > 0$ and constant, then $Pr(\textit{ATSP}(M) = \textit{AP}(M)) < 1 - \phi (c)$ for some positive function $\phi$. Finally, if $np_{n} \rightarrow 0$ then $Pr(\textit{ATSP}(M) = \textit{AP}(M)) \rightarrow 0$.

The Tutte-Grothendieck polynomial T(G; x, y) of a graph G encodes numerous interesting combinatorial quantities associated with the graph. Its evaluation in various points in the (x,y) plane gave the number of spanning forests of the graph, the number of its strongly connected orientations, the number of its proper k-colorings, the (all terminal) reliability probability of the graph, and various other invariants the exact computation of each of which is well known to be P-hard. Here we develop a general technique that supplies fully polynomial randomised approximation schemes for approximating the valve of T(G; x,, y) for any dense graph G, that is, any graph on n vertices whose minimum degree is /spl Omega/(n), whenever x/spl ges/1 and y/spl ges/1, and in various additional points. This region includes evaluations of reliability and partition functions of the ferromagnetic Q-state Potts model. Extensions to linear matroids where T specialises to the weight enumerator of linear codes are considered as well.>

Given an expander graph $G = (V,E)$ and a set of q disjoint pairs of vertices in V, the authors are interested in finding for each pair $(a_i ,b_i )$ a path connecting $a_i $ to $b_i $ such that the set of q paths so found is edge disjoint. (For general graphs the related decision problem is NP complete.) The authors prove sufficient conditions for the existence of edge-disjoint paths connecting any set of $q \leqslant {n / {(\log n)^\kappa }}$ disjoint pairs of vertices on any n vertex bounded degree expander, where $\kappa $ depends only on the expansion properties of the input graph, and not on n. Furthermore, a randomized $o(n^3 )$ time algorithm, and a random $\mathcal{NC}$ algorithm for constructing these paths is presented. (Previous existence proofs and construction algorithms allowed only up to $n^ \epsilon $ pairs, for some $ \epsilon \ll \frac{1}{3}$, and strong expanders [D. Peleg and E. Upfal, Combinatorica, 9 (1989), pp. 289–313.].) In passing, an algorithm is developed for splitting a sufficiently strong expander into two edge-disjoint spanning expanders.

Article Free Access Share on Separator based parallel divide and conquer in computational geometry Authors: Alan M. Frieze View Profile , Gary L. Miller View Profile , Shang-Hua Teng View Profile Authors Info & Claims SPAA '92: Proceedings of the fourth annual ACM symposium on Parallel algorithms and architecturesJune 1992 Pages 420–429https://doi.org/10.1145/140901.141934Published:01 June 1992Publication History 18citation296DownloadsMetricsTotal Citations18Total Downloads296Last 12 Months13Last 6 weeks6 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Given an expander graph G = (V, E) and a set of q disjoint pairs of vertices in V, we are interested in finding for each pair (ai, bi), a path connecting ai to bi, such that the set of q paths so found is edge-disjoint. (For general graphs the related decision problem is NPcomplete.) We prove sufficient conditions for the existence of edge-disjoint paths connecting any set of q ≤ n/(log n) κ disjoint pairs of vertices on any n vertex bounded degree expander, where κ depends only on the expansion properties of the input graph, and not on n. Furthermore, we present a randomized o(n 3) time algorithm, and a random N C algorithm for constructing these paths. (Previous existence proofs and construction algorithms allowed only up to n ǫ pairs, for some ǫ ≪ 1/3, and strong expanders [19].) In passing, we develop an algorithm for splitting a sufficiently strong expander into two edge-disjoint spanning expanders.

Article Finding hidden Hamiltonian cycles Share on Authors: Andrei Z. Broder DEC Systems Research Center, Palo Alto, CA DEC Systems Research Center, Palo Alto, CAView Profile , Alan M. Frieze Carnegie-Mellon Univ., Pittsburgh, PA Carnegie-Mellon Univ., Pittsburgh, PAView Profile , Eli Shamir Hebrew Univ., Jerusalem, Israel Hebrew Univ., Jerusalem, IsraelView Profile Authors Info & Claims STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of ComputingJanuary 1991 Pages 182–189https://doi.org/10.1145/103418.103442Online:03 January 1991Publication History 11citation341DownloadsMetricsTotal Citations11Total Downloads341Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

A randomized polynomial-time algorithm for approximating the volume of a convex body K in n -dimensional Euclidean space is presented. The proof of correctness of the algorithm relies on recent theory of rapidly mixing Markov chains and isoperimetric inequalities to show that a certain random walk can be used to sample nearly uniformly from within K .

The problem of finding a perfect matching of small total length in a complete graph whose vertices are points in the interval [0,1] is considered. The greedy heuristic for this problem repeatedly picks the two closest unmatched points x and y, and adds the edge $xy$ to the matching. It is shown that if $2n$ points are randomly chosen uniformly in $[0,1]$, then the expected length of the matching given by the greedy algorithm is $\theta (\log n)$. This compares unfavourably with the length of the shortest perfect matching, which is always less than 1.

We present a randomised polynomial time algorithm for approximating the volume of a convex body K in n-dimensional Euclidean space. The proof of correctness of the algorithm relies on recent theory of rapidly mixing Markov chains and isoperimetric inequalities to show that a certain random walk can be used to sample nearly uniformly from within K.

We show that computing the volume of a polyhedron given either as a list of facets or as a list of vertices is as hard as computing the permanent of a matrix.

We propose a general polynomial time algorithm to find small integer solutions to systems of linear congruences. We use this algorithm to obtain two polynomial time algorithms for reconstructing the values of variables $x_1 , \cdots ,x_k $ when we are given some linear congruences relating them together with some bits obtained by truncating the binary expansions of the variables. The first algorithm reconstructs the variables when either the high order bits or the low order bits of the $x_i $ are known. It is essentially optimal in its use of information in the sense that it will solve most problems almost as soon as the variables become uniquely determined by their constraints. The second algorithm reconstructs the variables when an arbitrary window of consecutive bits of the variables is known. This algorithm will solve most problems when twice as much information as that necessary to uniquely determine the variables is available. Two cryptanalytic applications of the algorithms are given: predicting linear congruential generators whose outputs are truncated and breaking the simplest version of Blum’s protocol for exchanging secrets.

Let edge weights for the complete graph on vertex set $\{ 1,2, \cdots ,n\} $ be chosen independently and uniformly from $\{ 0,1, \cdots ,B(n) - 1\} $ where $B(n) = o({n / {\log \log n}})$. We show that there exists a polynomial time $(O(n^3 \log n))$ algorithm which solves the associated travelling salesman problem with probability tending to 1 as n tends to $\infty $.

We give a simple analysis of an algorithm for solving subset-sum problems proposed by Lagarias and Odlyzko [2].

This paper describes a polynomial time algorithm HAM that searches for Hamilton cycles in undirected graphs. On a random graph its asymptotic probability of success is that of the existence of such a cycle. If all graphs with n vertices are considered equally likely, then using dynamic programming on failure leads to an algorithm with polynomial expected time. Finally, it is used in an algorithm for solving the symmetric bottleneck travelling salesman problem with probability tending to 1, as n tends to ∞.

One of the most popular and fast methods of generating "random" sequence are linear congruential generators. This paper discusses the predictability of the sequence given only a constant proportion /spl alpha/ of the leading bits of the first few numbers generated. We show that the rest of the sequence is predictable in polynomial time, almost always, provided /spl alpha/ > 2/5.

Abstract We consider the asymmetric traveling salesman problem for which the triangular inequality is satisfied. For various heuristics we construct examples to show that the worst‐case ratio of length of tour found to minimum length tour is (n) for n city problems. We also provide a new O([log2n]) heuristic.