Search

A common thread in all of the recent results concerning the testing of dense graphs is the use of Szemerédi's regularity lemma. In this paper we show that in some sense this is not a coincidence. Our first result is that the property defined by having any given Szemerédi-partition is testable with a constant number of queries. Our second and main result is a purely combinatorial characterization of the graph properties that are testable with a constant number of queries. This characterization (roughly) says that a graph property P can be tested with a constant number of queries if and only if testing P can be reduced to testing the property of satisfying one of finitely many Szemerédi-partitions. This means that in some sense, testing for Szemerédi-partitions is as hard as testing any testable graph property. We thus resolve one of the main open problems in the area of property-testing, which was first raised by Goldreich, Goldwasser, and Ron [J. ACM, 45 (1998), pp. 653-750] in the paper that initiated the study of graph property-testing. This characterization also gives an intuitive explanation as to what makes a graph property testable. [ABSTRACT FROM AUTHOR]

In 1996 Ivkovič and Lloyd [A fundamental restriction on fully dynamic maintenance of bin packing, Inform. Process. Lett., 59 (1996), pp. 229-232] gave the lower bound 4/3 on the asymptotic worst-case ratio for so-called fully dynamic bin packing algorithms, where the number of repackable items in each step is restricted by a constant. In this paper we improve this result to about 1.3871. We present our proof for a semionline case of the classical bin packing, but it works for fully dynamic bin packing as well. We prove the lower bound by analyzing and solving a specific optimization problem. The bound can be expressed exactly using the Lambert W function. [ABSTRACT FROM AUTHOR]

Sweeney--Robertson--Tocher (SRT) division, as it was discovered in the late 1950s, represented an important improvement in the speed of division algorithms for computers at the time. A variant of SRT division is still commonly implemented in computers today. Although some bounds on the performance of the original SRT division method were obtained, a great many questions remained unanswered. In this paper, the original version of SRT division is described as a dynamical system. This enables us to bring modern dynamical systems theory, a relatively new development in mathematics, to bear on an older problem. In doing so, we are able to show that SRT division is ergodic, and is even Bernoulli, for all real divisors and dividends. With the Bernoulli property, we are able to use entropy to prove that the natural extensions of SRT division are isomorphic by way of the Kolmogorov--Ornstein theorem. We demonstrate how our methods and results can be applied to a much larger class of division algorithms. [ABSTRACT FROM AUTHOR]

Property testing is a relaxation of classical decision problems which aims at distinguishing between functions having a predetermined property and functions being far from any function having the property. In this paper we present a novel framework for analyzing property testing algorithms. Our framework is based on a connection of property testing and a new class of problems which we call abstract combinatorial programs. We show that if the problem of testing a property can be reduced to an abstract combinatorial program of small dimension, then the property has an efficient tester. We apply our framework to a variety of problems. We present efficient property testing algorithms for geometric clustering problems, for the reversal distance problem, and for graph and hypergraph coloring problems. We also prove that, informally, any hereditary graph property can be efficiently tested if and only if it can be reduced to an abstract combinatorial program of small size. Our framework allows us to analyze all our testers in a unified way, and the obtained complexity bounds either match or improve the previously known bounds. Furthermore, even if the asymptotic complexity of the testers is not improved, the obtained proofs are significantly simpler than the previous ones. We believe that our framework will help to understand the structure of efficiently testable properties. [ABSTRACT FROM AUTHOR]

In this paper, we give the first approximation algorithm for the problem of max-min fair allocation of indivisible goods. An instance of this problem consists of a set of k people and m indivisible goods. Each person has a known linear utility function over the set of goods which might be different from the utility functions of other people. The goal is to distribute the goods among the people and maximize the minimum utility received by them. The approximation ratio of our algorithm is Ω(1/√k log3 k). As a crucial part of our algorithm, we design and analyze an iterative method for rounding a fractional matching on a tree which might be of independent interest. We also provide better bounds when we are allowed to exclude a small fraction of the people from the problem. [ABSTRACT FROM AUTHOR]

Let G = (V,E) be a weighted undirected graph having nonnegative edge weights. An estimate δˆ(u, v) of the actual distance d(u, v) between u, v ∈ V is said to be of stretch t if and only if δ(u, v) ≤ δˆ(u, v) = t · δ(u, v). Computing all-pairs small stretch distances efficiently (both in terms of time and space) is a well-studied problem in graph algorithms. We present a simple, novel, and generic scheme for all-pairs approximate shortest paths. Using this scheme and some new ideas and tools, we design faster algorithms for all-pairs t-stretch distances for a whole range of stretch t, and we also answer an open question posed by Thorup and Zwick in their seminal paper [J. ACM, 52 (2005), pp. 1-24]. [ABSTRACT FROM AUTHOR]

We study the maximum edge-disjoint paths problem in undirected planar graphs: given a graph G and node pairs (demands) s1t1, s2t2, … , sktk, the goal is to maximize the number of demands that can be connected (routed) by edge-disjoint paths. The natural multicommodity flow relaxation has an Ω(√n) integrality gap, where n is the number of nodes in G. Motivated by this, we consider solutions with small constant congestion c > 1, that is, solutions in which up to c paths are allowed to use an edge (alternatively, each edge has a capacity of c). In previous work we obtained an O(log n) approximation with congestion 2 via the flow relaxation. This was based on a method of decomposing into well-linked subproblems. In this paper we obtain an O(1) approximation with congestion 4. To obtain this improvement we develop an alternative decomposition that is specific to planar graphs. The decomposition produces instances that we call Okamura-Seymour (OS) instances. These have the property that all terminals lie on a single face. Another ingredient we develop is a constant factor approximation for the all-or-nothing flow problem on OS instances via the flow relaxation. [ABSTRACT FROM AUTHOR]

Suffix trees and suffix arrays are the most prominent full-text indices, and their construction algorithms are well studied. In the literature, the fastest algorithm runs in O(n) time, while it requires O(n log n)-bit working space, where n denotes the length of the text. On the other hand, the most space-efficient algorithm requires O(n)-bit working space while it runs in O(n log n) time. It was open whether these indices can be constructed in both o(n log n) time and o(n log n)- bit working space. This paper breaks the above time-and-space barrier under the unit-cost word RAM. We give an algorithm for constructing the suffix array, which takes O(n) time and O(n)-bit working space, for texts with constant-size alphabets. Note that both the time and the space bounds are optimal. For constructing the suffix tree, our algorithm requires O(n logϵ n) time and O(n)-bit working space for any 0 < ϵ < 1. Apart from that, our algorithm can also be adopted to build other existing full-text indices, such as compressed suffix tree, compressed suffix arrays, and FM-index. We also study the general case where the size of the alphabet Σ is not constant. Our algorithm can construct a suffix array and a suffix tree using optimal O(n log ∣Σ∣)-bit working space while running in O(n log log ∣Σ∣) time and O(n(logϵ n + log ∣Σ∣)) time, respectively. These are the first algorithms that achieve o(n log n) time with optimal working space. Moreover, for the special case where log ∣Σ∣ = O((log log n)1-ϵ), we can speed up our suffix array construction algorithm to the optimal O(n). [ABSTRACT FROM AUTHOR]

In this paper, an optimal linear-time algorithm is presented to solve the haplotype inference problem for pedigree data when there are no recombinations and the pedigree has no mating loops. The approach is based on the use of graphs to capture SNP, Mendelian, and parity constraints of the given pedigree. This representation allows us to capture the constraints as the edges in a graph, rather than as a system of linear equations as in previous approaches. Graph traversals are then used to resolve the parity of these edges, resulting in an optimal running time. [ABSTRACT FROM AUTHOR]

In this paper we consider the problem of constructing a small arithmetic circuit for a polynomial for which we have oracle access. Our focus is on n-variate polynomials, over a finite field F, that have depth-3 arithmetic circuits (with an addition gate at the top) with two multiplication gates of degree at most d. We obtain the following results: 1. Multilinear case. When the circuit is multilinear (multiplication gates compute multilinear polynomials) we give an algorithm that outputs, with probability 1 - o(1), all the depth-3 circuits with two multiplication gates computing the polynomial. The running time of the algorithm is poly(n, ∣F∣). 2. General case. When the circuit is not multilinear we give a quasi-polynomial (in n, d, ∣F∣) time algorithm that outputs, with probability 1-o(1), a succinct representation of the polynomial. In particular, if the depth-3 circuit for the polynomial is not of small depth-3 rank (namely, after removing the g.c.d. (greatest common divisor) of the two multiplication gates, the remaining linear functions span a not too small linear space), then we output the depth-3 circuit itself. In the case that the rank is small we output a depth-3 circuit with a quasi-polynomial number of multiplication gates. ... Prior to our work there have been several interpolation algorithms for restricted models. However, all the techniques used there completely fail when dealing with depth-3 circuits with even just two multiplication gates. Our proof technique is new and relies on the factorization algorithm for multivariate black-box polynomials, on lower bounds on the length of linear locally decodable codes with two queries, and on a theorem regarding the structure of identically zero depth-3 circuits with four multiplication gates. [ABSTRACT FROM AUTHOR]

Two graphs G and H on n vertices are ϵ-far from being isomorphic if at least ϵ(n 2) edges must be added or removed from E(G) in order to make G and H isomorphic. In this paper we deal with the question of how many queries are required to distinguish between the case that two graphs are isomorphic and the case that they are ϵ-far from being isomorphic. A query is defined as probing the adjacency matrix of any one of the two graphs, i.e., asking if a pair of vertices forms an edge of the graph or not. We investigate both one-sided and two-sided error testers under two possible settings: The first setting is where both graphs need to be queried, and the second setting is where one of the graphs is fully known to the algorithm in advance. We prove that the query complexity of the best one-sided error testing algorithm is Θ(n3/2) if both graphs need to be queried, and that it is Θ(n) if one of the graphs is known in advance (where the Θ notation hides polylogarithmic factors in the upper bounds). For two-sided error testers, we prove that the query complexity of the best tester is Θ(√n) when one of the graphs is known in advance, and we show that the query complexity lies between Θ(n) and Õ(n5/4) if both G and H need to be queried. All of our algorithms are additionally nonadaptive, while all of our lower bounds apply for adaptive testers as well as nonadaptive ones. [ABSTRACT FROM AUTHOR]

In this paper, we devise a special 1-error-correcting code that enables us to embed the graph product of an N/logN-node hypercube and a logN-node complete graph into in an N-node hypercube with constant load, dilation, and congestion. We apply the result to construct improved embeddings of trees and other structures in a hypercube, and to design more efficient and robust algorithms for reconfiguring a hypercube around random or worst-case faults. The result has also been used subsequently by others to show that the N-node hypercube can emulate all N-node planar graphs with constant slowdown. [ABSTRACT FROM AUTHOR]

Agreement is at the heart of distributed computing. In its simple form, it requires a set of processes to decide on a common value out of the values they propose. The time-complexity of distributed agreement problems is generally measured in terms of the number of communication rounds needed to achieve a global decision, i.e., for all nonfaulty (correct) processes to reach a decision. This paper studies the time-complexity of local decisions in agreement problems, which we define as the number of communication rounds needed for at least one correct process to decide. We explore bounds for early local decision that depend on the number f of actual failures (that occur in a given run of an algorithm), out of the maximum number t of failures tolerated (by the algorithm). We first consider the synchronous message-passing model where we give tight local decision bounds for three variants of agreement: consensus, uniform consensus, and (nonblocking) atomic commit. We use these results to (1) show that, for consensus, local decision bounds are not compatible with global decision bounds (roughly speaking, they cannot be reached by the same algorithm), and (2) draw the first sharp line between the time-complexity of uniform consensus and atomic commit. Then we consider the eventually synchronous model, where we give tight local decision bounds for synchronous runs of uniform consensus. (In this model, consensus and uniform consensus are similar, atomic commit is impossible, and one cannot bound the number of rounds to reach a decision in nonsynchronous runs of consensus algorithms.) We prove a counterintuitive result that the early local decision bound is the same as the early global decision bound. We also give a matching early deciding consensus algorithm that is significantly better than previous eventually synchronous consensus algorithms. [ABSTRACT FROM AUTHOR]

The design of new quantum algorithms has proven to be an extremely difficult task. This paper considers a different approach to this task by studying the problem of quantum state generation. We motivate this problem by showing that the entire class of statistical zero knowledge, which contains natural candidates for efficient quantum algorithms such as graph isomorphism and lattice problems, can be reduced to the problem of quantum state generation. To study quantum state generation, we define a paradigm which we call adiabatic state generation (ASG) and which is based on adiabatic quantum computation. The ASG paradigm is not meant to replace the standard quantum circuit model or to improve on it in terms of computational complexity. Rather, our goal is to provide a natural theoretical framework, in which quantum state generation algorithms could be designed. The new paradigm seems interesting due to its intriguing links to a variety of different areas: the analysis of spectral gaps and ground-states of Hamiltonians in physics, rapidly mixing Markov chains, adiabatic computation, and approximate counting. To initiate the study of ASG, we prove several general lemmas that can serve as tools when using this paradigm. We demonstrate the application of the paradigm by using it to turn a variety of (classical) approximate counting algorithms into efficient quantum state generators of nontrivial quantum states, including, for example, the uniform superposition over all perfect matchings in a bipartite graph. [ABSTRACT FROM AUTHOR]

Let S be a set of n points in ℝ². Given an integer 1 ≤ k ≤ n, we wish to find a maximally separated subset I ⊆ S of size k; this is a subset for which the minimum among the (2k) pairwise distances between its points is as large as possible. The decision problem associated with this problem is to determine whether there exists I ⊆ S, ∣I∣ = k, so that all (2k) pairwise distances in I are at least 2. This problem can also be formulated in terms of disk-intersection graphs: Let D be the set of unit disks centered at the points of S. The disk-intersection graph G of D has as edges all pairs of disks with nonempty intersection. Any set I with the above properties is then the set of centers of disks that form an independent set in the graph G. This problem is known to be NP-complete if k is part of the input. In this paper we first present a linear-time e-approximation algorithm for any constant k. Next we give exact algorithms for the cases k = 3 and k = 4 that run in time O(n4/3polylog(n)). We also present a simpler nO(√k)-time exact algorithm (as compared with the recent algorithm in [J. Alber and J. Fiala, J. Algorithms, 52 (2004), pp. 134-151]) for arbitrary values of k. [ABSTRACT FROM AUTHOR]

Almost all of the most successful quantum algorithms discovered to date exploit the ability of the Fourier transform to recover subgroup structures of functions, especially periodicity. The fact that Fourier transforms can also be used to capture shift structure has received far less attention in the context of quantum computation. In this paper, we present three examples of ‘unknown shift’ problems that can be solved efficiently on a quantum computer using the quantum Fourier transform. For one of these problems, the shifted Legendre symbol problem, we give evidence that the problem is hard to solve classically, by showing a reduction from breaking algebraically homomorphic cryptosystems. We also define the hidden coset problem, which generalizes the hidden shift problem and the hidden subgroup problem. This framework provides a unified way of viewing the ability of the Fourier transform to capture subgroup and shift structure. [ABSTRACT FROM AUTHOR]

Kernel-based linear-threshold algorithms, such as support vector machines and Perceptron-like algorithms, are among the best available techniques for solving pattern classification problems. In this paper, we describe an extension of the classical Perceptron algorithm, called second-order Perceptron, and analyze its performance within the mistake bound model of on-line learning. The bound achieved by our algorithm depends on the sensitivity to second-order data information and is the best known mistake bound for (efficient) kernel-based linear-threshold classifiers to date. This mistake bound, which strictly generalizes the well-known Perceptron bound, is expressed in terms of the eigenvalues of the empirical data correlation matrix and depends on a parameter controlling the sensitivity of the algorithm to the distribution of these eigenvalues. Since the optimal setting of this parameter is not known a priori, we also analyze two variants of the second-order Perceptron algorithm: one that adaptively sets the value of the parameter in terms of the number of mistakes made so far, and one that is parameterless, based on pseudoinverses. [ABSTRACT FROM AUTHOR]

In this paper we consider multiprocessor scheduling with hard deadlines and investigate the cost of eliminating migration in the online setting. Let I be any set of jobs that can be completed by some migratory offline schedule on m processors. We show that I can also be completed by a nonmigratory online schedule using m speed-5.828 processors (i.e., processors 5.828 times faster). This result supplements the previous results that I can also be completed by a nonmigratory offline schedule using 6m unit-speed processors [B. Kalyanasundaram and K. R. Pruhs, J. Algorithms, 38 (2001), pp. 2--24] or a migratory online schedule using m speed-2 processors [C. A. Phillips et al., Algorithmica, 32 (2002), pp. 163--200]. Our result is based on a simple conservative scheduling algorithm called PARK, which commits a processor to a job only when the processor has zero commitment before its deadline. A careful analysis of PARK further shows that the processor speed can be reduced arbitrarily close to 1 by exploiting more processors (say, using 16m speed-1.8 processors). PARK also finds application in overloaded systems; it gives the first online nonmigratory algorithm that can exploit moderately faster processors to match the performance of any migratory offline algorithm. [ABSTRACT FROM AUTHOR]

In this paper we consider the problem of testing bipartiteness of general graphs. The problem has previously been studied in two models, one most suitable for dense graphs and one most suitable for bounded-degree graphs. Roughly speaking, dense graphs can be tested for bipartiteness with constant complexity, while the complexity of testing bounded-degree graphs is [This symbol cannot be presented in ASCII format](√n), where n is the number of vertices in the graph (and [This symbol cannot be presented in ASCII format](f(n)) means Θ(f(n) · polylog(f(n)))). Thus there is a large gap between the complexity of testing in the two cases. In this work we bridge the gap described above. In particular, we study the problem of testing bipartiteness in a model that is suitable for all densities. We present an algorithm whose complexity is [This symbol cannot be presented in ASCII format](min(√n, n²/m)), where m is the number of edges in the graph, and we match it with an almost tight lower bound. [ABSTRACT FROM AUTHOR]

Given a multiset X = {x[SUB1],...,x[SUBn]} of real numbers, the floating-point set summation problem asks for S[SUBn] = x[SUB1] + ... x[SUBn]. Let E[SUP*,SUBn] denote the minimum worst-case error over all possible orderings of evaluating Sn. We prove that if X has both positive and negative numbers, it is NP-hard to compute S[SUBn] with the worst-case error equal to E[SUP*,SUBn] . We then give the first known polynomial-time approximation algorithm that has a provably small error for arbitrary X. Our algorithm incurs a worst-case error at most 2([log(n-1) + 1)E[SUP*, SUBn]. (All logarithms log in this paper are base 2.) After X is sorted, it runs in O(n) time. For the case where X is either all positive or all negative, we give another approximation algorithm with a worst-case error at most [log log n] E[SUP*,SUBn]. Even for unsorted X, this algorithm runs in O(n) time. Previously, the best linear-time approximation algorithm had a worst-case error at most [logn] E[SUP*,SUBn], while E[SUP*,SUBn] was known to be attainable in O(nlog n) time using Huffman coding. [ABSTRACT FROM AUTHOR]

This paper introduces the concept of precision-sensitive algorithms, analogous to the well-known output-sensitive algorithms. We exploit this idea in studying the complexity of the 3-dimensional Euclidean shortest path problem. Specifically, we analyze an incremental approximation approach and show that this approach yields an asymptotic improvement of running time. By using an optimization technique to improve paths on fixed edge sequences, we modify this algorithm to guarantee a relative error of O(2[SUP-r]) in a time polynomial in r and 1/δ where δdenotes the relative difference in path length between the shortest and the second shortest path. Our result is the best possible in some sense: if we have a strongly precision-sensitive algorithm, then we can show that unambiguous SAT (USAT) is in polynomial time, which is widely conjectured to be unlikely. Finally, we discuss the practicability of this approach. Experimental results are provided. [ABSTRACT FROM AUTHOR]

The present article concentrates on the dogleg-free Manhattan model where horizontal and vertical wire segments are positioned on di erent sides of the board and each net (wire) has at most one horizontal segment. While the minimum width can be found in linear time in the single row routing, apparently there was no e cient algorithm to find the minimum wire length. We show that there is no hope to find such an algorithm because this problem is NP -complete even if each net has only two terminals. The results on dogleg-free Manhattan routing can be connected with other application areas related to interval graphs. In this paper we define the minimum value interval placement problem. There is given a set of weighted intervals and w rows and the intervals have to be placed without overlapping into rows so that the sum of the interval values, which is the value of a function of the weight and the row number assigned to the interval, is minimum. We show that this problem is NP -complete. This implies the NP -completeness of other problems including the minimum wire length routing and the sum coloring on interval graphs. Key words: single row routing; VLSI; NP -complete problems; minimum wire length; interval graph [ABSTRACT FROM AUTHOR]

This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each neighbor with at least 2d+1 fewer tokens, where d is the maximum degree of any node in the network. We show that within O(δ/α) steps, the algorithm reduces the maximum difference in tokens between any two nodes to at most O((d[sup2] log n)/α), where δ is the global imbalance in tokens (i.e., the maximum difference between the number of tokens at any node initially and the average number of tokens), n is the number of nodes in the network, and α is the edge expansion of the network. The time bound is tight in the sense that for any graph with edge expansion α and for any value δ, there exists an initial distribution of tokens with imbalance δ for which the time to reduce the imbalance to even δ/2 is at least ω(&delta/α). The bound on the final imbalance is tight in the sense that there exists a class of networks that can be locally balanced everywhere (i.e., the maximum difference in tokens between any two neighbors is at most 2d), while the global imbalance remains ω((d[sup2] log n)/α). Furthermore, we show that upon reaching a state with a global imbalance of O((d[sup2] log n)/α), the time for this algorithm to locally balance the network can be as large as δ(n[sup½]). We extend our analysis to a variant of this algorithm for dynamic and asynchronous networks. We also present tight bounds for a randomized algorithm in which each node sends at most one token in each step. Key words: load balancing; distributed network algorithms [ABSTRACT FROM AUTHOR]

We present a deterministic (1+o(1))-approximation O(n1/2+o(1) + D1+o(1))-time algorithm for solving the single-source shortest paths problem on distributed weighted networks (the CONGEST model); here n is the number of nodes in the network and D is its (hop) diameter. This is the first non-trivial deterministic algorithm for this problem. It also improves (i) the running time of the randomized (1+o(1))-approximation Õ(√n1/2D1/4+D)-time algorithm of Nanongkai [STOC 2014] by a factor of as large as n1/8, and (ii) the O(є-1logє-1)-approximation factor of Lenzen and Patt-Shamir's Õ(n1/2+є+D)-time algorithm [STOC 2013, pp. 381-390] within the same running time. (Throughout, we use Õ(.) to hide polylogarithmic factors in n.) Our running time matches the known time lower bound of Ω(√n/log n + D) [M. Elkin, SIAM J. Comput., 36 (2006), pp. 433-456], thus essentially settling the status of this problem which was raised at least a decade ago [M. Elkin, SIGACT News, 35 (2004), pp. 40-57]. It also implies a (2+o(1))-approximation O(n1/2+o(1)+D1+o(1))-time algorithm for approximating a network's weighted diameter which almost matches the lower bound by Holzer and Pinsker [in Proceedings of OPODIS, 2015, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Germany, 2016, 6]. In achieving this result, we develop two techniques which might be of independent interest and useful in other settings: (i) a deterministic process that replaces the "hitting set argument" commonly used for shortest paths computation in various settings, and (ii) a simple, deterministic construction of an (no(1), o(1))-hop set of size n1+o(1). We combine these techniques with many distributed algorithmic techniques, some of which are from problems that are not directly related to shortest paths, e.g., ruling sets [A. V. Goldberg, S. A. Plotkin, and G. E. Shannon, SIAM J. Discrete Math., 1 (1988), pp. 434-446], source detection [C. Lenzen and D. Peleg, in Proceedings of PODC, 2013, pp. 375-382], and partial distance estimation [C. Lenzen and B. Patt-Shamir, in Proceedings of PODC, 2015, pp. 153-162]. Our hop set construction also leads to single-source shortest paths algorithms in two other settings: (i) a (1+o(1))-approximation no(1)-time algorithm on congested cliques, and (ii) a (1+o(1))-approximation no(1)-pass n1+o(1)-space streaming algorithm. The first result answers an open problem in [D. Nanongkai, in Proceedings of STOC, 2014, pp. 565-573]. The second result partially answers an open problem raised by McGregor in 2006 [List of Open Problems in Sublinear Algorithms: Problem 14]. [ABSTRACT FROM AUTHOR]

Phylogenetic tree reconstruction is a fundamental biological problem. Quartet amalgamation--combining a set of trees over four taxa into a tree over the full set of taxa--stands at the core of many phylogenetic reconstruction methods. This task has attracted many theoretical as well as practical works. However, even reconstruction from a consistent set of quartet trees is NP-hard, and the best approximation ratio known is 1/3. Despite its importance, the only rigorous results for approximating quartets are the naive 1/3 approximation that applies to the general case and a polynomial time approximation scheme (PTAS) when the input is the complete set of all (n 4) possible quartets. Even when it is possible to determine the correct quartet induced by every four taxa, the time needed to generate the complete set of all quartets may be impractical. A faster approach is to sample at random just m « (n 4) quartets and provide this sample as an input. In this work we present the first polynomial time approximation algorithm whose expected guaranteed approximation is strictly better than 1/3 when the input is any random sample of m consistent quartets. The approximation ratio of the algorithm is greater than 0.425. An important ingredient in our algorithm involves solving a weighted maximum cut problem in a certain weighted graph that corresponds to the set of input quartets. Our second main result generalizes the aforementioned PTAS algorithm to handle dense, rather than complete, inputs. [ABSTRACT FROM AUTHOR]

We obtain randomized algorithms for factoring degree n univariate polynomials over 픽 requiring O(n1.5+o(1) log 1+o(1)q + n1+o(1)log2+o(1) q) bit operations. When log q < n, this is asymptotically faster than the best previous algorithms [J. von zur Gathen and V. Shoup, Comput. Complexity, 2 (1992), pp. 187-224; E. Kaltofen and V. Shoup, Math. Comp., 67 (1998), pp. 1179- 1197]; for log q ≥ n, it matches the asymptotic running time of the best known algorithms. The improvements come from new algorithms for modular composition of degree n univariate polynomials, which is the asymptotic bottleneck in fast algorithms for factoring polynomials over finite fields. The best previous algorithms for modular composition use O(n(ω+1)/2) field operations, where ω is the exponent of matrix multiplication [R. P. Brent and H. T. Kung, J. Assoc. Comput. Mach., 25 (1978), pp. 581-595], with a slight improvement in the exponent achieved by employing fast rectangular matrix multiplication [X. Huang and V. Y. Pan, J. Complexity, 14 (1998), pp. 257- 299]. We show that modular composition and multipoint evaluation of multivariate polynomials are essentially equivalent, in the sense that an algorithm for one achieving exponent α implies an algorithm for the other with exponent α+o(1), and vice versa. We then give two new algorithms that solve the problem near-optimally: an algebraic algorithm for fields of characteristic at most no(1), and a nonalgebraic algorithm that works in arbitrary characteristic. The latter algorithm works by lifting to characteristic 0, applying a small number of rounds of multimodular reduction, and finishing with a small number of multidimensional FFTs. The final evaluations are reconstructed using the Chinese remainder theorem. As a bonus, this algorithm produces a very efficient data structure supporting polynomial evaluation queries, which is of independent interest. Our algorithms use techniques that are commonly employed in practice, in contrast to all previous subquadratic algorithms for these problems, which relied on fast matrix multiplication. [ABSTRACT FROM AUTHOR]

Given dissimilarity data on pairs of objects in a set, we study the problem of fitting a tree metric to this data so as to minimize additive error (i.e., some measure of the difference between the tree metric and the given data). This problem arises in constructing an M-level hierarchical clustering of objects (or an ultrametric on objects) so as to match the given dissimilarity data--a basic problem in statistics. Viewed in this way, the problem is a generalization of the correlation clustering problem (which corresponds to M = 1). We give a very simple randomized combinatorial algorithm for the M-level hierarchical clustering problem that achieves all approximation ratio of M + 2. This is a generalization of a previous factor 3 algorithm for correlation clustering on complete graphs. The problem of fitting tree metrics also arises in phylogeny where the objective is to learn the evolution tree by fitting a tree to dissimilarity data on taxa. The quality of the fit is measured by taking the lp norm of the difference between the tree metric constructed and the given data. Previous results obtained a factor 3 approximation for finding the closest tree metric under the l ∞ norm. No nontrivial approximation for general lp norms was known before. We present a novel linear program formulation for this problem and obtain an O((log n log log n)1/p)-approximation to the closest ultrametric under the lp norm using this. Our techniques are based on representing and viewing an ultrametric as a hierarchy of clusterings and may be useful in other contexts. [ABSTRACT FROM AUTHOR]

Let Φ be a uniformly distributed random k-SAT formula with n variables and m clauses. We present a polynomial time algorithm that finds a satisfying assignment of Φ with high probability for constraint densities m/n < (1 - ϵk)2k ln(k)/k, where ϵk → 0. Previously no efficient algorithm was known to find satisfying assignments with a nonvanishing probability beyond m/n = 1.817 · 2k/k [A. Frieze and S. Suen, J. Algorithms, 20 (1996), pp. 312-355]. [ABSTRACT FROM AUTHOR]

We establish a bound of O(n2k1+ϵ), for any ϵ > 0, on the combinatorial complexity of the set T of line transversals of a collection P of k convex polyhedra in ℝ3 with a total of n facets, and we present a randomized algorithm which computes the boundary of T in comparable expected time. Thus, when k ⪡ n, the new bounds on the complexity (and construction cost) of T improve upon the previously best known bounds, which are nearly cubic in n. To obtain the above result, we study the set Tℓ0 of line transversals which emanate from a fixed line ℓ0, establish an almost tight bound of O(nk1+ϵ) on the complexity of ℓ0 , and provide a randomized algorithm which computes ℓ0 in comparable expected time. Slightly improved combinatorial bounds for the complexity of ℓ0 and comparable improvements in the cost of constructing this set are established for two special cases, both assuming that the polyhedra of P are pairwise disjoint: the case where ℓ0 is disjoint from the polyhedra of P, and the case where the polyhedra of P are unbounded in a direction parallel to ℓ0. Our result is related to the problem of bounding the number of geometric permutations of a collection C of k pairwise-disjoint convex sets in ℝ3, namely, the number of distinct orders in which the line transversals of C visit its members. We obtain a new partial result on this problem. [ABSTRACT FROM AUTHOR]

We introduce a new low-distortion embedding of ℣2d into ℣pO(log n) (p = 1, 2) called the fast Johnson-Lindenstrauss transform (FJLT). The FJLT is faster than standard random projections and just as easy to implement. It is based upon the preconditioning of a sparse projection matrix with a randomized Fourier transform. Sparse random projections are unsuitable for low-distortion embeddings. We overcome this handicap by exploiting the "Heisenberg principle" of the Fourier transform, i.e., its local-global duality. The FJLT can be used to speed up search algorithms based on low-distortion embeddings in ℣1 and ℣2. We consider the case of approximate nearest neighbors in ℣2d. We provide a faster algorithm using classical projections, which we then speed up further by plugging in the FJLT. We also give a faster algorithm for searching over the hypercube. [ABSTRACT FROM AUTHOR]

We develop the algorithmic theory of vertex separators and its relation to the embeddings of certain metric spaces. Unlike in the edge case, we show that embeddings into L1 (and even Euclidean embeddings) are insufficient but that the additional structure provided by many embedding theorems does suffice for our purposes. We obtain an O(√log n) approximation for minimum ratio vertex cuts in general graphs, based on a new semidefinite relaxation of the problem, and a tight analysis of the integrality gap which is shown to be Θ(√log n). We also prove an optimal O(log k)-approximate max-flow/min-vertex-cut theorem for arbitrary vertex-capacitated multicommodity flow instances on k terminals. For uniform instances on any excluded-minor family of graphs, we improve this to O(1), and this yields a constant-factor approximation for minimum ratio vertex cuts in such graphs. Previously, this was known only for planar graphs, and for general excluded-minor families the best known ratio was O(log n). These results have a number of applications. We exhibit an O(√log n) pseudoapproximation for finding balanced vertex separators in general graphs. In fact, we achieve an approximation ratio of O(√log opt), where opt is the size of an optimal separator, improving over the previous best bound of O(log opt). Likewise, we obtain improved approximation ratios for treewidth: in any graph of treewidth k, we show how to find a tree decomposition of width at most O(k√log k), whereas previous algorithms yielded O(k log k). For graphs excluding a fixed graph as a minor (which includes, e.g., bounded genus graphs), we give a constant-factor approximation for the treewidth. This in turn can be used to obtain polynomial-time approximation schemes for several problems in such graphs. [ABSTRACT FROM AUTHOR]

We present a deterministic O(log n log log n) space algorithm for undirected st-connectivity. It is based on a space-efficient simulation of the deterministic EREW algorithm of Chong and Lam [J. Algorithms, 18 (1995), pp. 378-402], an approach suggested by Prof. Vijaya Ramachandran, and uses the universal exploration sequences for trees constructed by Koucký in [Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001, pp. 21-27]. Our result improves the O(log4/3 n) bound of Armoni et al. in [Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1997, pp. 230-239] and is a big step towards the optimal O(log n). Independently of our result and using a different set of techniques, the optimal bound was achieved by Reingold in [Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005, pp. 376-385]. [ABSTRACT FROM AUTHOR]

We consider the rooted orienteering problem: Given a set P of n points in the plane, a starting point r ∊ P, and a length constraint B, one needs to find a path starting from r that visits as many points of P as possible and of length not exceeding B. We present a (1 - ϵ)-approximation algorithm for this problem that runs in nO(1/ϵ) time; the computed path visits at least (1 - ϵ)kopt points of P, where kopt is the number of points visited by an optimal solution. This is the first polynomial time approximation scheme for this problem. The algorithm also works in higher dimensions. [ABSTRACT FROM AUTHOR]

We present new results for three problems dealing with a set P of n convex constant-complexity fat polyhedra in ³-space. (i) We describe a data structure for vertical ray shooting in P that has O(log² n) query time and uses O(n log² n) storage. (ii) We give an algorithm to compute in O(n log³ n) time a depth order on P if it exists. (iii) We give an algorithm to verify in O(n log³ n) time whether a given order on P is a valid depth order. All three results improve on previous results. [ABSTRACT FROM AUTHOR]

For circuit classes R, the fundamental computational problem Min-R asks for the minimum R-size of a Boolean function presented as a truth table. Prominent examples of this problem include Min-DNF, which asks whether a given Boolean function presented as a truth table has a k-term disjunctive normal form (DNF), and Min-Circuit (also called the minimum circuit size problem (MCSP)), which asks whether a Boolean function presented as a truth table has a size k Boolean circuit. We present a new reduction proving that Min-DNF is NP-complete. It is significantly simpler than the known reduction of Masek [Some NP-Complete Set Covering Problems, manuscript, 1979], which is from Circuit-SAT. We then give a more complex reduction, yielding the result that Min-DNF cannot be approximated to within a factor smaller than (log N)γ, for some constant γ > 0, assuming that NP is not contained in quasi-polynomial time. The standard greedy algorithm for Set Cover is often used in practice to approximate Min-DNF. The question of whether Min-DNF can be approximated to within a factor of o(log N) remains open, but we construct an instance of Min-DNF on which the solution produced by the greedy algorithm is Ω(log N) larger than optimal. Finally, we turn to the question of approximating circuit size for slightly more general classes of circuits. DNF formulas are depth-two circuits of AND and OR gates. Depth-d circuits are denoted by ACd0. We show that it is hard to approximate the size of ACd0 circuits (for large enough d) under cryptographic assumptions. [ABSTRACT FROM AUTHOR]

We present a structural characterization of all tournaments T = (V,A) such that, for any nonnegative integral weight function defined on V , the maximum size of a feedback vertex set packing is equal to the minimum weight of a triangle in T. We also answer a question of Frank by showing that it is NP-complete to decide whether the vertex set of a given tournament can be partitioned into two feedback vertex sets. In addition, we give exact and approximation algorithms for the feedback vertex set packing problem on tournaments. [ABSTRACT FROM AUTHOR]

We give an algorithm that learns any monotone Boolean function f : {-1, 1}n → {-1, 1} to any constant accuracy, under the uniform distribution, in time polynomial in n and in the decision tree size of f. This is the first algorithm that can learn arbitrary monotone Boolean functions to high accuracy, using random examples only, in time polynomial in a reasonable measure of the complexity of f. A key ingredient of the result is a new bound showing that the average sensitivity of any monotone function computed by a decision tree of size s must be at most √log s. This bound has proved to be of independent utility in the study of decision tree complexity [O. Schramm, R. O'Donnell, M. Saks, and R. Servedio, Every decision tree has an influential variable, in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 2005, pp. 31-39]. We generalize the basic inequality and learning result described above in various ways-specifically, to partition size (a stronger complexity measure than decision tree size), p-biased measures over the Boolean cube (rather than just the uniform distribution), and real-valued (rather than just Boolean-valued) functions. [ABSTRACT FROM AUTHOR]

We consider a generalization of edge coloring bipartite graphs in which every edge has a weight in [0, 1] and the coloring of the edges must satisfy that the sum of the weights of the edges incident to a vertex v of any color must be at most 1. For unit weights, König's theorem says that the number of colors needed is exactly the maximum degree. For this generalization, we show that 2.557n + o(n) colors are sufficient, where n is the maximum total weight adjacent to any vertex, improving the previously best bound of 2.833n + O(1) due to Du et al. Our analysis is interesting on its own and involves a novel decomposition result for bipartite graphs and the introduction of an associated continuous one-dimensional bin packing instance which we can prove allows perfect packing. This question is motivated by the question of the rearrangeability of 3-stage Clos networks. In that context, the corresponding parameter n of interest in the edge coloring problem is the maximum over all vertices of the number of unit-sized bins needed to pack the weights of the incident edges. In that setting, we are able to improve the bound to 2.5480n + o(n), also improving a bound of 2.5625n + O(1) of Du et al. We also consider the online version of this problem in which edges have to be colored as soon as they are revealed. In this context, we can show that 5n colors are enough. This contrasts with the best known lower bound of 3n - 2 by Tsai, Wang, and Hwang but improves upon the previous best upper bound of 5.75n obtained by Gao and Hwang. Additionally, we show several improved bounds for more restricted versions of the problem. These online bounds are achieved by simple and easy-to-implement algorithms, inspired by the first fit heuristic for bin packing. [ABSTRACT FROM AUTHOR]

We present an algorithm to enumerate the pointed pseudotriangulations of a given point set, based on the greedy flip algorithm of Pocchiola and Vegter [Discrete Comput. Geom. 16 (1996), pp. 419-453]. Our two independent implementations agree and allow us to experimentally verify or disprove conjectures on the numbers of pointed pseudotriangulations and triangulations of a given point set. (For example, we establish that the number of triangulations is bounded by the number of pointed pseudotriangulations for all sets of up to 10 points.) [ABSTRACT FROM AUTHOR]

In many optimization problems, one seeks to allocate a limited set of resources to a set of individuals with demands. Thus, such allocations can naturally be viewed as vectors, with one coordinate representing each individual. Motivated by work in network routing and bandwidth assignment, we consider the problem of producing solutions that simultaneously approximate all feasible allocations in a coordinate-wise sense. This is a very strong type of ‘global’ approximation guarantee, and we explore its consequences in a wide range of discrete optimization problems, including facility location, scheduling, and bandwidth assignment in networks. A fundamental issue—one not encountered in the traditional design of approximation algorithms—is that good approximations in this global sense need not exist for every problem instance; there is no a priori reason why there should be an allocation that simultaneously approximates all others. As a result, the existential questions concerning such good allocations lead to a new perspective on a number of fundamental problems in resource allocation, and on the structure of their feasible solutions. [ABSTRACT FROM AUTHOR]

Jackson and Wormald conjecture that if G is a 3-connected n-vertex graph with maximum degree d ≥ 4, then G has a cycle of length Ω(nlogd-1 ²). We show that this conjecture holds when d - 1 is replaced by max{64, 4d + 1}. Our proof implies a cubic algorithm for finding such a cycle. [ABSTRACT FROM AUTHOR]

We present a new scheme for computing shortest paths on real-weighted undirected graphs in the fundamental comparison-addition model. In an efficient preprocessing phase our algorithm creates a linear-size structure that facilitates single-source shortest path computations in O (m log $\alpha$) time, where $\alpha$ = $\alpha$(m, n) is the very slowly growing inverse-Ackermann function, m the number of edges, and n the number of vertices. As special cases our algorithm implies new bounds on both the all-pairs and single-source shortest paths problems. We solve the all-pairs problem in O (mn log $\alpha$(m, n)) time and, if the ratio between the maximum and minimum edge lengths is bounded by n (log n) O (1), we can solve the single-source problem in O (m + n log log n) time. Both these results are theoretical improvements over Dijkstra's algorithm, which was the previous best for real weighted undirected graphs. Our algorithm takes the hierarchy-based approach invented by Thorup. [ABSTRACT FROM AUTHOR]

We present several applications of quantum amplitude amplification for deciding whether all elements in the image of a given function are distinct, for finding an intersection of two sorted tables, and for finding a triangle in a graph. Our techniques generalize and improve those of Brassard, Hoyer, and Tapp [ACM SIGACT News, 28 (1997), pp. 14--19]. This shows that in the quantum world element distinctness is significantly easier than sorting, in contrast to the classical world. [ABSTRACT FROM AUTHOR]

A finite collection of x-monotone unbounded Jordan curves in the plane is called a family of pseudo-lines if every pair of curves intersect in at most one point, and the two curves cross each other there. Let L be such a collection of n pseudo-lines, and let P be a set of m points in $\reals^2$. Extending a result of Goodman [Discrete Math., 32 (1980), pp. 27--35], we define a duality transform that maps L to a set L* of points in $\reals^2$ and P to a set P* of (x-monotone) pseudo-lines in $\reals^2$, so that the incidence and the "above-below" relations between the points and the pseudo-lines are preserved. We present an efficient algorithm for computing the dual arrangement {\eus A}$(P^*)$ under an appropriate model of computation. We also present a dynamic data structure for reporting, in $O(m^\eps + k)$ time, all k points of P that lie below a query arc, which is either a circular arc or a portion of the graph of a polynomial of fixed degree. This result is needed for computing the dual arrangement for certain classes of pseudo-lines arising in several applications, but is also interesting in its own right. We present a few applications of our dual arrangement algorithm, such as computing incidences between points and pseudo-lines and computing a subset of faces in a pseudo-line arrangement. Next, we present an efficient algorithm for cutting a set of circles into arcs so that every pair of arcs intersect in at most one point, i.e., the resulting arcs constitute a collection of pseudo-segments. By combining this algorithm with our algorithm for computing the dual arrangement of pseudo-lines, we obtain efficient algorithms for several problems involving arrangements of circles or circular arcs, such as reporting or counting incidences between points and circles and computing a set of marked faces in arrangements of circles. [ABSTRACT FROM AUTHOR]

We present a new analysis of the worst-case cost of path compression, which is an operation that is used in various well-known "union-find" algorithms. In contrast to previous analyses which are essentially based on bottom-up approaches, our method proceeds top-down, yielding recurrence relations from which the various bounds arise naturally. In particular the famous quasi-linear bound involving the inverse Ackermann function can be derived without having to introduce the Ackermann function itself. [ABSTRACT FROM AUTHOR]

The article discusses perfectness with respect to an elusive graph property. It mentions a graph property as elusive if every algorithm for testing this property has to read in the worst case entries of the adjacency matrix of the given graph. Several graph properties are elusive including planarity and k-colorability. An overview of several theorems related to perfect graphs is presented. It discusses the strategies used for constructing a bicritically perfect graph for n number of nodes. It concludes that perfectness, a hereditary graph property, is elusive.

For the random binary search tree with it nodes inserted the number of ancestors of the elements with ranks k and ℓ, 1 ≤ k < ℓ ≤ n, as well as the path distance between these elements in the tree are considered. For both quantities, central limit theorems for appropriately rescaled versions are derived. For the path distance, the condition ℓ - k → ∞ as n → ∞ is required. We obtain tail bounds and the order of higher moments for the path distance. The path distance measures the complexity of finger search in the tree. [ABSTRACT FROM AUTHOR]

Motivated by a frequency assignment problem in cellular networks, we introduce and study a new coloring problem that we call minimum conflict-free coloring (min-CF-coloring). In its general form, the input of the min-CF-coloring problem is a set system (X, S), where each S &epsiv; S is a subset of X. The output is a coloring x of the sets in S that satisfies the following constraint: for every x &epsiv; X there exists a color i and a unique set S &epsiv; S such that x &epsiv; S and x(S) = i. The goal is to minimize the number of colors used by the coloring x. Min-CF-coloring of general set systems is not easier than the classic graph coloring problem. However, in view of our motivation, we consider set systems induced by simple geometric regions in the plane. In particular, we study disks (both congruent and noncongruent), axis-parallel rectangles (with a constant ratio between the smallest and largest rectangle), regular hexagons (with a constant ratio between the smallest and largest hexagon), and general congruent centrally symmetric convex regions in the plane. In all cases we have coloring algorithms that use O(log n) colors (where n is the number of regions). Tightness is demonstrated by showing that even in the case of unit disks, θ(log n) colors may be necessary. For rectangles and hexagons we also obtain a constant-ratio approximation algorithm when the ratio between the largest and smallest rectangle (hexagon) is a constant. We also consider a dual problem of CF-coloring points with respect to sets. Given a set system (X, S), the goal in the dual problem is to color the elements in X with a minimum number of colors so that every set S &epsiv; S contains a point whose color appears only once in S. We show that O(log lXI) colors suffice for set systems in which X is a set of points in the plane and the sets are intersections of X with scaled translations of a convex region. [ABSTRACT FROM AUTHOR]

We consider suffix tree construction for situations with missing suffix links. Two examples of such situations are suffix trees for parameterized strings and suffix trees for two-dimensional arrays. These trees also have the property that the node degrees may be large. We add a new back- propagation component to MeCreight's algorithm and also give a high probability hashing scheme for large degrees. We show that these two features enable construction of suffix trees for general sit- uations with missing suffix links in O(n) time, with high probability. This gives the first randomized linear time algorithm for constructing suffix trees for parameterized strings. [ABSTRACT FROM AUTHOR]

Analyzes a simple dynamic work-stealing algorithm. Generator-allocation function of the algorithm; Number of tasks which are transferred from the nonempty processor to the empty processor; Long-term behavior of the system; ; Upper bounds on the average system load.