In a series of four papers we prove the following relaxation of the Loebl--Komlós--Sós conjecture: For every $\alpha>0$ there exists a number $k_0$ such that for every $k>k_0$, every $n$-vertex graph $G$ with at least $(\frac{1}{2}+\alpha)n$ vertices of degree at least $(1+\alpha)k$ contains each tree $T$ of order $k$ as a subgraph. The method to prove our result follows a strategy similar to approaches that employ the Szemerédi regularity lemma: We decompose the graph $G$, find a suitable combinatorial structure inside the decomposition, and then embed the tree $T$ into $G$ using this structure. Since for sparse graphs $G$, the decomposition given by the regularity lemma is not helpful, we use a more general decomposition technique. We show that each graph can be decomposed into vertices of huge degree, regular pairs (in the sense of the regularity lemma), and two other objects each exhibiting certain expansion properties. In this paper, we introduce this novel decomposition technique. In the three follow-up papers, we find a suitable combinatorial structure inside the decomposition, which we then use for embedding the tree.

This is the second of a series of four papers in which we prove the following relaxation of the Loebl--Komlós--Sós conjecture: For every $\alpha>0$ there exists a number $k_0$ such that for every $k>k_0$, every $n$-vertex graph $G$ with at least $(\frac{1}{2}+\alpha)n$ vertices of degree at least $(1+\alpha)k$ contains each tree $T$ of order $k$ as a subgraph. In the first paper of this series, we gave a decomposition of the graph $G$ into several parts of different characteristics; this decomposition might be viewed as an analogue of a regular partition for sparse graphs. In the present paper, we find a combinatorial structure inside this decomposition. In the third and fourth papers, we refine the structure and use it for embedding the tree $T$.

This is the third of a series of four papers in which we prove the following relaxation of the Loebl--Komlós--Sós conjecture: For every $\alpha>0$ there exists a number $k_0$ such that for every $k>k_0$, every $n$-vertex graph $G$ with at least $(\frac12+\alpha)n$ vertices of degree at least $(1+\alpha)k$ contains each tree $T$ of order $k$ as a subgraph. In the first paper of the series, we gave a decomposition of the graph $G$ into several parts of different characteristics. In the second paper, we found a combinatorial structure inside the decomposition. In this paper, we will give a refinement of this structure. In the fourth paper, the refined structure will be used for embedding the tree $T$.

This is the last of a series of four papers in which we prove the following relaxation of the Loebl--Komlós--Sós conjecture: For every $\alpha>0$ there exists a number $k_0$ such that for every $k>k_0$, every $n$-vertex graph $G$ with at least $(\frac12+\alpha)n$ vertices of degree at least $(1+\alpha)k$ contains each tree $T$ of order $k$ as a subgraph. In the first two papers of this series, we decomposed the host graph $G$ and found a suitable combinatorial structure inside the decomposition. In the third paper, we refined this structure and proved that any graph satisfying the conditions of the above approximate version of the Loebl--Komlós--Sós conjecture contains one of ten specific configurations. In this paper we embed the tree $T$ in each of the ten configurations.

For any positive integers r and n, let H(r,n) denote the family of graphs on n vertices with maximum degree r, and let H(r,n,n) denote the family of bipartite graphs H on 2n vertices with n vertices in each vertex class, and with maximum degree r. On one hand, we note that any H(r,n)-universal graph must have /spl Omega/(n/sup 2-2/r/) edges. On the other hand, for any n/spl ges/n/sub 0/(r), we explicitly construct H(r,n)-universal graphs G and /spl Lambda/ on n and 2n vertices, and with O(n/sup 2-/spl Omega//(1/r log r)) and O(n/sup 2-1/r/ log/sup 1/r/ n) edges, respectively, such that we can efficiently find a copy of any H /spl epsiv/ H (r,n) in G deterministically. We also achieve sparse universal graphs using random constructions. Finally, we show that the bipartite random graph G=G(n,n,p), with p=cn/sup -1/2r/ log/sup 1/2r/ n is fault-tolerant; for a large enough constant c, even after deleting any /spl alpha/-fraction of the edges of G, the resulting graph is still H(r,/spl alpha/(/spl alpha/)n,/spl alpha/(/spl alpha/)n)-universal for some /spl alpha/: [0,1)/spl rarr/(0,1].

Given a set of n nuts of distinct widths and a set of n bolts such that each nut corresponds to a unique bolt of the same width, how should we match every nut with its corresponding bolt by comparing nuts with bolts? (No comparison is allowed between two nuts or two bolts.) The problem can be naturally viewed as a variant of the classic sorting problem as follows. Given two lists of n numbers each such that one list is a permutation of the other, how should we sort the lists by comparisons only between numbers in different lists? We give an O(n log n)-time deterministic algorithm for the problem. This is optimal up to a constant factor and answers an open question posed by Alon et al. [Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, 1994, pp. 690--696]. Moreover, when copies of nuts and bolts are allowed, our algorithm runs in optimal O(log n) time on n processors in Valiant's parallel comparison tree model. Our algorithm is based on the AKS sorting algorithm with substantial modifications.

We establish a lower bound of (1:12 \\Gamma o(1)) n log n on the size of any n-input sorting network; this is the first lower bound that improves upon the trivial information-theoretic bound by more than a lower order term. We then extend the lower bound to comparator networks that approximately sort a certain fraction of all input permutations. We also prove a lower bound of (c \\Gamma o(1)) log n, where c ß 3:27, on the depth of any sorting network; the best previous result of approximately (2:41 \\Gamma o(1)) log n was established by Yao in 1980. Our result for size is based on a new technique that lower bounds the number of "0--1 collisions " in the network; we provide strong evidence that the technique will lead to even better lower bounds. 1 Part of this work was done while the author was at DIMACS. 2 XEROX Palo Alto Research Center, 3333 Coyote Hill Road, Palo Alto, CA 94304. Partially supported by the NSF under grant CCR-9404113. Email: [email protected]. 3 Department o...

Given a graph G on n nodes the authors say that a graph T on n + k nodes is a k-fault tolerant version of G, if one can embed G in any n node induced subgraph of T. Thus T can sustain k faults and still emulate G without any performance degradation. They show that for a wide range of values of n, k and d, for any graph on n nodes with maximum degree d there is a k-fault tolerant graph with maximum degree O(kd). They provide lower bounds as well: there are graphs G with maximum degree d such that any k-fault tolerant version of them has maximum degree at least Ω(d√k)

The authors investigate the asymptotic efficiency of certain combinatorial networks called halvers, which are basic building blocks of many parallel algorithms. They improve the efficiency of halvers in terms of their depth. The novelty is the use of combinatorial circuits whose basic units are k-sorter switches.>

The authors present a deterministic algorithm for the connectivity problem on undirected graphs that runs in O(log/sup 1.5/n) space. Thus, the recursive doubling technique of Savich (1970) which requires Theta (log/sup 2/n) space is not optimal for this problem.>

A theorem of Brooks guarantees that a maximum-degree-D graph can be properly colored with D colors if the graph does not contain a large complete subgraph. It is proved that finding such a coloring is in NC.

Given a set S of n points, a subset X of size k is called a k-set if there is a hyperplane II that separates X from X/sup c/. It is proved that O(n square root k/log/sub */k) is an upper bound for the number of k-sets in the plane, thus improving the previous bound of P. Erdos et al. (A Survey of Combinatorial Theory, North-Holland, 1983, p.139-49) by a factor of log/sub */k. The method can be extended to give the bound O(n square root k/(log k)/sup epsilon /). The proof only establishes the weaker result; it uses the geometry and combinatorics together in a stronger way than in the earlier work.>

Article Free Access Share on On the second eigenvalue of random regular graphs Authors: J. Friedman Department of Computer Science, Princeton University, Princeton, NJ Department of Computer Science, Princeton University, Princeton, NJView Profile , J. Kahn Dept. of Mathematics and Center for O. R., Rutgers University, New Brunswick, NJ Dept. of Mathematics and Center for O. R., Rutgers University, New Brunswick, NJView Profile , E. Szemerédi Dept. of Computer Science, Rutgers University, New Brunswick, NJ and Mathematical Institute of the Hungarian Academy of Sciences Dept. of Computer Science, Rutgers University, New Brunswick, NJ and Mathematical Institute of the Hungarian Academy of SciencesView Profile Authors Info & Claims STOC '89: Proceedings of the twenty-first annual ACM symposium on Theory of computingFebruary 1989 Pages 587–598https://doi.org/10.1145/73007.73063Published:01 February 1989Publication History 104citation2,261DownloadsMetricsTotal Citations104Total Downloads2,261Last 12 Months122Last 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

We show that the following statements are equivalent: Statement 1. 3-pushdown graphs have sublinear separators. Statement 1∗. k-page graphs have sublinear separators. Statement 2. A one-tape nondeterministic Turing machine can simulate a two-tape machine in subquadratic time. None of the statements is known to be true or false at present. However, our proof of equivalence is quantitative-it relates exactly the separator size of the two kinds of graphs to the running time of the simulation in Statement 2. Using this equivalence we derive several graph-theoretic corollaries. There are known examples where upper bounds on graph properties imply upper bounds on computation time or space. There are other examples where lower bounds on graph properties are used to derive lower bounds on computation time in restricted settings. However, our results may constitute the first example where a graph problem is shown to be equivalent to a problem in computational complexity. In a companion paper we construct graphs and prove a lower bound or their separators. Using the equivalence we prove an almost linear lower bound for the size of separators for 3-pushdown graphs and an almost quadratic lower bound for simulating two-tape nondeterministic Turing machines by one-tape machines. Specifically, for an integers s let ls(n), the s-iterated logarithm function, be defined inductively: l°(n)=n, ls+1(n)=log2(ls(n)) for s⩾0. Then: For every fixed s and all n, there is an n-vertex 3-pushdown graph whose smallest separator contains at least ω(n/ls(n)) vertices. There is a language L recognizable in real time by a two-tape nondeterministic Turing machine, but every on-line one-tape nondeterministic Turing machine that recognizes L requires ω(n2/ls(n)) time for any positive integer.

Given n points in the plane and an integer k, the problem of selecting that pair of points that determines the line with the kth smallest or largest slope is considered. In the restricted case, where k is $O(n)$, line sweeping gives an optimal, $O(n\log n)$-time algorithm. For general k the parametric search technique of Megiddo is used to describe an $O(n(\log n)^2 )$-time algorithm. This is modified to produce a new, optimal $O(n\log n)$-time selection algorithm by incorporating an approximation idea.

This paper presents a comparison sorting algorithm for the abstract CROW PRAM parallel computer model. The algorithm sorts n input values using n processors and runs in time $O(\log n/\log \log n)$ on the average, assuming that all permutations of the input are equally likely.

Infinite sets P and Q of primes are described, P ⊂ Q. For any natural number n it can be decided if n ∈ P in (deterministic) time Ο((log n)9). This answers affirmatively the question of whether there exists an infinite set of primes whose membership can be tested in polynomial time, and is the main result of the paper. Also, for every n ∈ Q, we show how to produce at random, in expected time Ο((log n)3), a certificate of length Ο(log n) which can be verified in (deterministic) time Ο((log n)3); this is less than the time needed for two exponentiations and is much faster than existing methods. Finally it is important that P is relatively dense (at least cn2/3/log n elements less than n). Elements of Q in a given range may be generated quickly, but it would be costly for an adversary to search Q in this range; this could be useful in cryptography.

For every choice of positive integers c and k such that k ≥ 3 and c 2 - k ≥ 0.7, there is a positive number ε such that, with probability tending to 1 as n tends to ∞, a randomly chosen family of cn clauses of size k over n variables is unsatisfiable, but every resolution proof of its unsatisfiability must generate at least (1 + ε) n clauses.

We consider the problem of element distinctness. Here n synchronized processors, each given an integer input, must decide whether these integers are pairwise distinct, while communicating via an infinitely large shared memory. If simultaneous write access to a memory cell is forbidden, then a lower bound of $\Omega ( \log n )$ on the number of steps easily follows (from S. Cook, C. Dwork, and R. Reischuk, SIAM J. Comput., 15 (1986), pp. 87–97.) When several (different) values can be written simultaneously to any cell, then there is an simple algorithm requiring $O ( 1 )$ steps. We consider the intermediate model, in which simultaneous writes to a single cell are allowed only if all values written are equal. We prove a lower bound of $\Omega ( ( \log n )^{1 /2} )$ steps, improving the previous lower bound of $\Omega ( \log \log \log n )$ steps (F. E. Fich, F. Meyer auf der Heide, and A. Wigderson, Adv. in Comput., 4 (1987), pp. 1–15). The proof uses Ramsey-theoretic and combinatorial arguments. The result implies a separation between the powers of some variants of the PRAM model of parallel computation.

In this paper we show that a wide class of probabilistic algorithms can be simulated by deterministic algorithms. Namely if there is a test in LOGSPACE so that a random sequence of length (log n)2 / log log n passes the test with probability at least 1/n then a deterministic sequence can be constructed in LOGSPACE which also passes the test. It is important that the machine performing the test gets each bit of the sequence only once. The theorem remains valid if both the test and the machine constructing the satisfying sequence have access to the same oracle of polynomial size.

We prove the first superlinear lower bound for a concrete decision problem in P on a Turing machine with one work tape and a two-way input tape (also called: off-line 1-tape Turing machine). In particular we show for off-line Turing machines that 2 tapes are better than 1 and that 3 pushdown stores are better than 2 (both in the deterministic and in the nondeterministic case).

The first result concerns branching programs having width (log n) °{*).We give an fl(n log n~ log log n) lower bound for the size of such branching programs computing almost any symmetric Boolean fnnction and in particular the following explicit fnnction: "the sum of the input variables is a quadratic residue mod p" where p is any given prime between n 1/4 and n 1/3.This is a strengthening of previous nonlinear lower bounds obtained by Chandra, Furst, Lipton and by Pudlgk.We mention that by iterating our method the result can be further strengthened to lfl(nlog n).The second result is a C" lower bound for read-onceonly branching programs computing an explicit Boolean function.For n = (~), the function computes the parity of the number of triangles in a graph on v vertices.This improves previous exp(cx/n ) lower bounds for other graph functions by Wegener and Z£k.The result implies a linear lower bound for the space complexity of this Boolean function on "eraser machines", i.e. machines that erase each input bit immediately after having read it.

We show that in the deterministic comparison model for parallel computation, n processors can select the k th smallest item from a set of n numbers in O(loglogn) parallel time.With this result all comparison tasks (selection, merging, sorting), now have upper and lower bounds of the same order in both random and deterministic models.

We show that the following statements are equivalent :Statement 1: 3-pushdown graphs have sublinear separators.

We build a theory of black box groups, and apply it to matrix groups over finite fields. Elements of a black box group are encoded by strings of uniform length and group operations are performd by an oracle. Subgroups are given by a list of generators. We prove that for such subgroups, membership and divisor of the order are in NPB. (B is the group box oracle.) Under a plausible mathematical hypothesis on short presentations of finite simple groups, nom membership and exaact order will also be in NPBand thus in NPB∩ NPB.

A data structure for representing a set of n items from a umverse of m items, which uses space n + o(n) and accommodates membership queries m constant time is described.Both the data structure and the query algorithm are easy to ~mplement.

We show that, for multi-tape Turing machines, non-deterministic linear time is more powerful than deterministic linear time. We also discuss the prospects for extending this result to more general Turing machines.

The purpose of this paper is to describe a sorting network of size 0(n log n) and depth 0(log n).

We describe a data structure for representing a set of n items from a universe of m items, which uses space n+o(n) and accommodates membership queries in constant time. Both the data structure and the query algorithm are easy to implement.

In this paper we analyze the performance of a well known algorithm known as double hashing [Knuth]. In this method we probe the hash table along arithmetic progressions, where both the initial element and the increment of the progression are chosen randomly and independently depending only on the key K of the search. We prove that double hashing is asymptotically equivalent to uniform probing, an idealized hashing technique that exhibits no clustering and is known to be optimal in a certain sense. Between steps of the extension process we can show that the effect of clustering is negligible, and that we therefore never depart too far from the truly random situation.