On the complexity of planar Boolean circuits

We consider planar circuits, formulas and multilective planar circuits. It is shown that planar circuits and formulas are incomparable. An (n logn) lower bound is given for the multilective planar circuit complexity of a decision problem and an (n ^3/2) lower bound is given for the multilective planar circuit complexity of a multiple output function.     

Circuits constructed with MOD q gates cannot compute “AND” in sublinear size

Algebraic techniques are used to prove that any circuit constructed with MOD _q gates that computes the AND function must use (n) gates at the first level. The best bound previously known to be valid for arbitraryq was (logn).     

A lower bound for sorting networks based on the shuffle permutation

We prove an (lg² n/lg lgn) lower bound for the depth ofn-input sorting networks based on the shuffle permutation. The best previously known lower bound was the trivial (lgn) bound, while the best upper bound is given by Batcher's (lg² n)-depth bitonic sorting network. The proof technique employed in the lower bound argument may be of independent interest.C. G. Plaxton was supported by NSF Research Initiation Award CCR-9111591, and the Texas Advanced Research Program under Grant No. 003658-480. T. Suel was supported by the Texas Advanced Research Program under Grant No. 003658-480, and by an MCD Fellowship of the University of Texas at Austin.     

On communication-bounded synchronized alternating finite automata

We continue the study of communication-bounded synchronized alternating finite automata (SAFA), first considered by Hromkovi et al. We show that to accept a nonregular language, an SAFA needs to generate at least (log logn) communication symbols infinitely often; furthermore, a synchronized alternating finite automaton without nondeterminism (SUFA) needs to generate at least(log logn) communication symbols infinitely often for some constantk1. We also show that these bounds are tight.Next, we establish dense hierarchies of these machines on the function bounding the number of communication symbols. Finally, we give a characterization of NP in terms of communication-bounded multihead synchronized alternating finite automata, namely, NP = _k1 L(SAFA(k-heads,n ^k -com)). This result recasts the relationships between P, NP, and PSPACE in terms of multihead synchronized alternating finite automata.Research supported in part by NSF Grant CCR89-18409     

Beating the Logarithmic Lower Bound: Randomized Preemptive Disjoint Paths and Call Control Algorithms

We consider the maximum disjoint paths problem and its generalization, the call control problem, in the on-line setting. In the maximum disjoint paths problem, we are given a sequence of connection requests for some communication network. Each request consists of a pair of nodes, that wish to communicate over a path in the network. The request has to be immediately connected or rejected, and the goal is to maximize the number of connected pairs, such that no two paths share an edge. In the call control problem, each request has an additional bandwidth specification, and the goal is to maximize the total bandwidth of the connected pairs (throughput), while satisfying the bandwidth constraints (assuming each edge has unit capacity). These classical problems are central in routing and admission control in high speed networks and in optical networks.We present the first known constant-competitive algorithms for both problems on the line. This settles an open problem of Garay et al. and of Leonardi. Moreover, to the best of our knowledge, all previous algorithms for any of these problems, are (logn)-competitive, where n is the number of vertices in the network (and obviously noncompetitive for the continuous line). Our algorithms are randomized and preemptive. Our results should be contrasted with the (logn) lower bounds for deterministic preemptive algorithms of Garay et al. and the (logn) lower bounds for randomized non-preemptive algorithms of Lipton and Tomkins and Awerbuch et al. Interestingly, nonconstant lower bounds were proved by Canetti and Irani for randomized preemptive algorithms for related problems but not for these exact problems.     

Tight bounds for oblivious routing in the hypercube

We prove that in anyN-node communication network with maximum degreed, any deterministic oblivious algorithm for routing an arbitrary permutation requires (N/d) parallel communication steps in the worst case. This is an improvement upon the (N/d ^3/2) bound obtained by Borodin and Hopcroft. For theN-node hypercube, in particular, we show a matching upper bound by exhibiting a deterministic oblivious algorithm that routes any permutation in (N/logN) steps. The best previously known upper bound was (N). Our algorithm may be practical for smallN (up to about 2¹⁴ nodes).C. Kaklamanis was supported in part by NSF Grant NSF-CCR-87-04513. T. Tsantilas was supported in part by NSF Grants NSF-DCR-86-00379 and NSF-CCR-89-02500.     

An optimal parallel algorithm for triangulating a set of points in the plane

This paper presents an optimal parallel algorithm for triangulating an arbitrary set ofn points in the plane. The algorithm runs inO(logn) time usingO(n) space andO(_n) processors on a Concurrent-Read, Exclusive-Write Parallel RAM model (CREW PRAM). The parallel lower bound on triangulation is (logn) time so the best possible linear speedup has been achieved. A parallel divide-and-conquer technique of subdividing a problem into subproblems is employed.     

Branch-and-bound and backtrack search on mesh-connected arrays of processors

In this paper we investigate the parallel complexity of backtrack and branch-and-bound search on the mesh-connected array. We present an (dN/logdN) lower bound for the time needed by arandomized algorithm to perform backtrack and branch-and-bound search of a tree of depthd on the N × N mesh, even when the depth of the tree is known in advance. The lower bound also holds for algorithms that are allowed to move tree-nodes and create multiple copies of the same tree-node.For the upper bounds we givedeterministic algorithms that are within a factor of 0(log^3/2 N) from our lower bound. Our algorithms do not make any assumption on the shape of the tree to be searched, do not know the depth of the tree in advance, and do not move tree-nodes nor create multiple copies of the same node.The best previously known algorithm for backtrack search on the mesh was randomized and required (dN/ logN) time. Our algorithm for branch-and-bound is the first algorithm that performs branch-and-bound search on a sparse network. Both the lower and the upper bounds extend to meshes of higher dimensions.Part of this work was done while the authors were at Harvard University.     

Parallel general prefix computations with geometric,algebraic, and other applications

We introduce a generic problem component that captures the most common, difficult kernel of many problems. This kernel involves general prefix computations (GPC). GPC's lower bound complexity of (n logn) time is established, and we give optimal solutions on the sequential model inO(n logn) time, on the CREW PRAM model inO(logn) time, on the BSR (broadcasting with selective reduction) model in constant time, and on mesh-connected computers inO(n) time, all withn processors, plus anO(log² n) time solution on the hypercube model. We show that GPC techniques can be applied to a wide variety of geometric (point set and tree) problems, including triangulation of point sets, two-set dominance counting, ECDF searching, finding two-and three-dimensional maximal points, the reconstruction of trees from their traversals, counting inversions in a permutation, and matching parentheses.work partially supported by NSF IRI/8709726work partially supported by NSERC.     

Parallel geometric algorithms on a mesh-connected computer

We show that a number of geometric problems can be solved on a n × n mesh-connected computer (MCC) inO(n) time, which is optimal to within a constant factor, since a nontrivial data movement on an MCC requires (n) time. The problems studied here include multipoint location, planar point location, trapezoidal decomposition, intersection detection, intersection of two convex polygons, Voronoi diagram, the largest empty circle, the smallest enclosing circle, etc. TheO(n) algorithms for all of the above problems are based on the classical divide-and-conquer problem-solving strategy.This work was supported in part by the National Science Foundation under Grant DCR 8420814. A preliminary version was presented in the 1987 FJCC, Dallas, TX.     

A Fat Boundary Method for the Poisson Problem in a Domain with Holes

We consider the Poisson equation with Dirichlet boundary conditions, in a domain , where ⁿ , and B is a collection of smooth open subsets (typically balls). The objective is to split the initial problem into two parts: a problem set in the whole domain , for which fast solvers can be used, and local subproblems set in narrow domains around the connected components of B, which can be solved in a fully parallel way. We shall present here a method based on a multi-domain formulation of the initial problem, which leads to a fixed point algorithm. The convergence of the algorithm is established, under some conditions on a relaxation parameter . The dependence of the convergence interval for upon the geometry is investigated. Some 2D computations based on a finite element discretization of both global and local problems are presented.     

Approximate motion planning and the complexity of the boundary of the union of simple geometric figures

We study rigid motions of a rectangle amidst polygonal obstacles. The best known algorithms for this problem have a running time of (n ²), wheren is the number of obstacle corners. We introduce thetightness of a motion-planning problem as a measure of the difficulty of a planning problem in an intuitive sense and describe an algorithm with a running time ofO((a/b · 1/_crit + 1)n(logn)²), wherea b are the lengths of the sides of a rectangle and _crit is the tightness of the problem. We show further that the complexity (= number of vertices) of the boundary ofn bow ties (see Figure 1) isO(n). Similar results for the union of other simple geometric figures such as triangles and wedges are also presented.This work was supported partially by the DFG Schwerpunkt Datenstrukturen und Algorithmen, Grants Me 620/6 and Al 253/1, and by the ESPRIT II Basic Research Actions Program of the EC under Contract No. 3075 (project ALCOM).     

A lower bound on the area of permutation layouts

In this paper we prove a tight (n ³) lower bound on the area of rectilinear grids which allow a permutation layout ofn inputs andn outputs. Previously, the best lower bound for the area of permutation layouts with arbitrary placement of the inputs and outputs was (n ²), though Cutler and Shiloach [CS] proved an (n ^2.5) lower bound for permutation layouts in which the set of inputs and the set of outputs each lie on horizontal lines. Our lower bound also holds for permutation layouts in multilayer grids as long as a fixed fraction of the paths do not change layers.The first author's research was partially supported by NSF Grant No. MCS 820-5167. The third author's research was supported by NSF Grant No. MCS-8204246 and by a Hebrew University Fellowship.     

The input/output complexity of transitive closure

Suppose a directed graph has its arcs stored in secondary memory, and we wish to compute its transitive closure, also storing the result in secondary memory. We assume that an amount of main memory capable of holdings values is available, and thats lies betweenn, the number of nodes of the graph, ande, the number of arcs. The cost measure we use for algorithms is theI/O complexity of Kung and Hong, where we count 1 every time a value is moved into main memory from secondary memory, or vice versa.In the dense case, wheree is close ton ², we show that I/O equal toO(n ³/s) is sufficient to compute the transitive closure of ann-node graph, using main memory of sizes. Moreover, it is necessary for any algorithm that is standard, in a sense to be defined precisely in the paper. Roughly, standard means that paths are constructed only by concatenating arcs and previously discovered paths. For the sparse case, we show that I/O equal toO(n ²e/s) is sufficient, although the algorithm we propose meets our definition of standard only if the underlying graph is acyclic. We also show that(n ²e/s) is necessary for any standard algorithm in the sparse case. That settles the I/O complexity of the sparse/acyclic case, for standard algorithms. It is unknown whether this complexity can be achieved in the sparse, cyclic case, by a standard algorithm, and it is unknown whether the bound can be beaten by nonstandard algorithms.We then consider a special kind of standard algorithm, in which paths are constructed only by concatenating arcs and old paths, never by concatenating two old paths. This restriction seems essential if we are to take advantage of sparseness. Unfortunately, we show that almost another factor ofn I/O is necessary. That is, there is an algorithm in this class using I/OO(n ³e/s) for arbitrary sparse graphs, including cyclic ones. Moreover, every algorithm in the restricted class must use(n ³e/s/log³ n) I/O, on some cyclic graphs.The work of this author was partially supported by NSF grant IRI-87-22886, IBM contract 476816, Air Force grant AFOSR-88-0266 and a Guggenheim fellowship.     

Quantum Algorithms for Highly Structured Search Problems

We consider the problem of identifying a base k string given an oracle which returns information about the number of correct components in a query, specifically, the Hamming distance between the query and the solution, modulo r = max{2, 6 – k}. Classically this problem requires (nlog _r k) queries. For k {2, 3, 4}, we construct quantum algorithms requiring only a single quantum query. For k > 4, we show that O(k) quantum queries suffice. In both cases the quantum algorithms are optimal. PACS: 03.67.Lx     

On problem transformability in VLSI

The two basic performance parameters that capture the complexity of any VLSI chip are the area of the chip,A, and the computation time,T. A systematic approach for establishing lower bounds onA is presented. This approach relatesA to the bisection flow, . A theory of problem transformation based on , which captures bothAT ² andA complexity, is developed. A fundamental problem, namely, element uniqueness, is chosen as a computational prototype. It is shown under general input/output protocol assumptions that any chip that decides ifn elements (each with (1+)lognbits) are unique must have =(nlogn), and thus, AT²=(n ²log² n), andA= (nlogn). A theory of VLSI transformability reveals the inherentAT ² andA complexity of a large class of related problems.This work was supported in part by the Semiconductor Research Corporation under contract RSCH 84-06-049-6.     

An optimal time bound for oblivious routing

The problem of routing data packets in a constant-degree network is considered. A routing scheme is calledoblivious if the route taken by each packet is uniquely determined by its source and destination. The time required for the oblivious routing ofn packets onn processors is known to be (n). It is demonstrated that the presence of extra processors can expedite oblivious routing. More specifically, the time required for the oblivious routing ofn packets onp processors is (n/p + logn).     

Algorithms for dense graphs and networks on the random access computer

We improve upon the running time of several graph and network algorithms when applied to dense graphs. In particular, we show how to compute on a machine with word size = (logn) a maximal matching in ann-vertex bipartite graph in timeO(n ²+n ^2.5/)=O(n ^2.5/logn), how to compute the transitive closure of a digraph withn vertices andm edges in timeO(n ²+nm/), how to solve the uncapacitated transportation problem with integer costs in the range [O.C] and integer demands in the range [–U.U] in timeO ((n ³ (log log/logn)^1/2+n² logU) lognC), and how to solve the assignment problem with integer costs in the range [O.C] in timeO(n ^2.5 lognC/(logn/loglogn)^1/4).Assuming a suitably compressed input, we also show how to do depth-first and breadth-first search and how to compute strongly connected components and biconnected components in timeO(n+n ²/), and how to solve the single source shortest-path problem with integer costs in the range [O.C] in time0 (n ²(logC)/logn). For the transitive closure algorithm we also report on the experiences with an implementation.Most of this research was carried out while both authors worked at the Fachbereich Informatik, Universität des Saarlandes, Saarbrücken, Germany. The research was supported in part by ESPRIT Project No. 3075 ALCOM. The first author acknowledges support also from NSERC Grant No. OGPIN007.     

A note on dense and nondense families of complexity classes

In a model for a measure of computational complexity, , for a partial recursive functiont, letR _t denote all partial recursive functions having the same domain ast and computable within timet. Let = {R _t |t is recursive} and let = { |_i is actually the running time function of a computation}. and are partially ordered under set-theoretic inclusion. These partial orderings have been extensively investigated by Borodin, Constable and Hopcroft in [3]. In this paper we present a simple uniform proof of some of their results. For example, we give a procedure for easily calculating a model of computational complexity for which is not dense while is dense. In our opinion, our technique is so transparent that it indicates that certain questions of density are not intrinsically interesting for general abstract measures of computational complexity, . (This is not to say that similar questions are necessarily uninteresting for specific models.)Supported by NSF Research Grants GP6120 and GJ27127.     

Lower bounds for set intersection queries

We consider the followingset intersection reporting problem. We have a collection of initially empty sets and would like to process an intermixed sequence ofn updates (insertions into and deletions from individual sets) andq queries (reporting the intersection of two sets). We cast this problem in thearithmetic model of computation of Fredman [F1] and Yao [Ya2] and show that any algorithm that fits in this model must take time (q+nq) to process a sequence ofn updates andq queries, ignoring factors that are polynomial in logn. We also show that this bound is tight in this model of computation, again to within a polynomial in logn factor, improving upon a result of Yellin [Ye]. Furthermore, we consider the caseq=O(n) with an additional space restriction. We only allow the use ofm memory locations, wherem n^3/2. We show a tight bound of (n²/m^1/3) for a sequence ofn operations, again ignoring the polynomial in logn factors.