Variable Order Panel Clustering

We present a new version of the panel clustering method for a sparse representation of boundary integral equations. Instead of applying the algorithm separately for each matrix row (as in the classical version of the algorithm) we employ more general block partitionings. Furthermore, a variable order of approximation is used depending on the size of blocks. We apply this algorithm to a second kind Fredholm integral equation and show that the complexity of the method only depends linearly on the number, say n, of unknowns. The complexity of the classical matrix oriented approach is O(n ²) while, for the classical panel clustering algorithm, it is O(nlog⁷ n). Received July 28, 1999; revised September 21, 1999     

An Improved Stability Bound for Binary Exponential Backoff

Goodman, Greenberg, Madras and March gave a lower bound of n ^{-Ω(log n} ) for the maximum arrival rate for which the n -user binary exponential backoff protocol is stable. Thus, they showed that the protocol is stable as long as the arrival rate is at most n ^{-Ω(log n} ) . We improve the lower bound, showing that the protocol is stable for arrival rates up to O(n ^-(0.75+δ) ) , for any δ>0 . Received October 15, 1999, and in final form November 13, 2000. Online publication February 26, 2001.     

Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs

We present an efficient algorithm for 4-coloring perfect planar graphs. The best previously known algorithm for this problem takesO(n ^3/2) sequential time, orO(log⁴ n) parallel time withO(n³) processors. The sequential implementation of our algorithm takesO(n logn) time. The parallel implementation of our algorithm takesO(log³ n) time withO(n) processors on a PRAM.     

An improved algorithm on the content of realizable fuzzy matrices

An n×nn{\times}n fuzzy matrix A is called realizable if there exists an n×tn{\times}t fuzzy matrix B such that A=B\odot B^T,A=B\odot B^{T}, where \odot\odot is the max–min composition. Let r(A)=min{p:A=B\odot B^T, B ? L^n×p}.r(A)={min}\{p:A=B\odot B^{T}, B\in L^{n\times p}\}. Then r(A)r(A) is called the content of A. Since 1982, how to calculate r(A) for a given n×nn{\times}n realizable fuzzy matrix A was a focus problem, many researchers have made a lot of research work. X. P. Wang in 1999 gave an algorithm to find the fuzzy matrix B and calculate r(A) within [r(A)]ⁿ²[r(A)]^{n^{2}} steps. Therefore, to find a simpler algorithm is a problem what we have to consider. This paper makes use of the symmetry of the realizable fuzzy matrix A to simplify the algorithm of content r(A)r(A) based on the work of Wang (Chin Ann Math A 6: 701–706, 1999).     

Worst case performance analysis of the two dimensional binary buddy system ∗

The worst case performance of the two dimensional binary buddy system is investigated. Tight lower bounds are given for two system performance measures, namely NETREQ and NETALLOC. Let the system size be 2 ⁿ × 2 ⁿ . It is shown that for any unrestricted saturating sequence S, we have NETREQ(S)≧4^[n/2] + 4^{[n/2] ? 1}+2^[n/2]+l and NETALLOC(S)≧4^[n/2] + 4^[n/2]; for any allocation-only saturating sequence S, we have NETALLOC(S)≧4 ⁿ + 1 and NETREQ(S)≧4 ^n?1 + 2 ⁿ + 2.     

An Efficient Output-Size Sensitive Parallel Algorithm for Hidden-Surface Removal for Terrains

We describe an efficient parallel algorithm for hidden-surface removal for terrain maps. The algorithm runs in O(log ⁴ n) steps on the CREW PRAM model with a work bound of O((n+k) \polylog ( n)) where n and k are the input and output sizes, respectively. In order to achieve the work bound we use a number of techniques, among which our use of persistent data structures is somewhat novel in the context of parallel algorithms. Received July 29, 1998; revised October 5, 1999.     

An Efficient Algorithm for Generating Prüfer Codes from Labelled Trees

According to Cayley's tree formula, there are n ^n-2 labelled trees on n vertices. Prüfer gave a bijection between the set of labelled trees on n vertices and sequences of n-2 numbers, each in the range 1, 2, ..., n . Such a number sequence is called a Prüfer code. The straightforward implementation of his bijection takes O(n log n ) time. In this paper we propose an O(n) time algorithm for the same problem. Our algorithm can be easily parallelized so that a Prüfer code can be generated in O (log n ) time using O(n) processors on the EREW PRAM computational model. Received October 2, 1998, and in final form March 1, 1999.     

Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs

We present an efficient algorithm for 4-coloring perfect planar graphs. The best previously known algorithm for this problem takesO(n ^3/2) sequential time, orO(log⁴ n) parallel time withO(n³) processors. The sequential implementation of our algorithm takesO(n logn) time. The parallel implementation of our algorithm takesO(log³ n) time withO(n) processors on a PRAM.

     

VISOR: Vast Independence System Optimization Routine

An algorithm is sketched that generates all K maximal independent sets and all M minimal dependent sets of an arbitrary independence system, based on a set of cardinality n having at most 2 ⁿ subsets, with access to an oracle that decides if a set is independent or not. Because the algorithm generates all those sets, it solves the problems of finding all maximum independent and minimum dependent sets. Those problems are known to be impossible to solve in general in time polynomial in n , K , and M , and they are \cal N \cal P hard. The algorithm proposed and used is efficient in the sense that it requires only O(nK+M) or O(K+nM) visits to the oracle, the nonpolynomial part is only related to bitstring comparisons and the like, which can be performed rather quickly and, to some degree, in parallel on a sequential machine. This complexity compares favorably with another algorithm that is O(n ² K ² ) . The design of a computer routine that implements the algorithm in a highly optimized way is discussed. The routine behaves as expected, as is shown by numerical experiments on a range of randomly generated independence systems with n up to n=34 . Application on an engineering design problem with n=28 shows the routine requires almost 10 ⁶ times less visits to the oracle than an exhaustive search, while the time spent in visiting the oracle is still significantly larger than that spent for all other computations together. Received March 30, 1998; revised February 10, 1999 and April 27, 1999.     

New Fixed-Parameter Algorithms for the Minimum Quartet Inconsistency Problem

Let S be a set of n taxa. Given a parameter k and a set of quartet topologies Q over S such that there is exactly one topology for every subset of four taxa, the parameterized Minimum Quartet Inconsistency (MQI) problem is to decide whether we can find an evolutionary tree inducing a set of quartet topologies that differs from the given set in at most k quartet topologies. The best fixed-parameter algorithm devised so far for the parameterized MQI problem runs in time O(4 ^k n+n ⁴). In this paper, first we present an O(3.0446 ^k n+n ⁴) fixed-parameter algorithm and an O(2.0162 ^k n ³+n ⁵) fixed-parameter algorithm for the parameterized MQI problem. Finally, we give an O ^*((1+ε) ^k ) fixed-parameter algorithm, where ε>0 is an arbitrarily small constant.     

Orthogonal queries in segments

We consider theorthgonal clipping problem in a set of segments: Given a set ofn segments ind-dimensional space, we preprocess them into a data structure such that given an orthogonal query window, the segments intersecting it can be counted/reported efficiently. We show that the efficiency of the data structure significantly depends on a geometric discrete parameterK named theProjected-image complexity, which becomes Θ(n ²) in the worst case but practically much smaller. If we useO(m) space, whereK log^4d−7 n≥m≥n log^4d−7 n, the query time isO((K/m)^1/2 log^{max{4, 4d−5}} n). This is near to an Ω((K/m)^1/2) lower bound.     

Efficient randomized generation of optimal algorithms for multiplication in certain finite fields

LetN _max(q) denote the maximum number of points of an elliptic curve over F _q . Given a prime powerq=p ^f and an integern satisfying 1/2q+1<n(N _max(q)–2)/2, we present an algorithm which on inputq andn produces an optimal bilinear algorithm of length 2n for multiplication in F _q ⁿ /F _q . The algorithm takes roughlyO(q ⁴+n ⁴logq) F _q -operations or equivalentlyO((q ⁴+n ⁴logq)f ²log² p) bit-operations to compute the output data.     

A Superlogarithmic Lower Bound for Shuffle-Unshuffle Sorting Networks

Shuffle-unshuffle sorting networks are a class of comparator networks whose structure maps efficiently to the hypercube and any of its bounded degree variants. Recently, n -input shuffle-unshuffle sorting networks with depth have been discovered. These networks are the only known sorting networks of depth o( lg ² n) that are not based on expanders, and their existence raises the question of whether a depth of O( lg n) can be achieved by any shuffle-unshuffle sorting network. In this paper we resolve this question by establishing an Ω( lg n lg lg n/lg lg lg n) lower bound on the depth of any n -input shuffle-unshuffle sorting network. Our lower bound can be extended to certain restricted classes of nonoblivious sorting algorithms on hypercubic machines. Received September 9, 1999, and in final form December 20, 1999.     

Communication complexity towards lower bounds on circuit depth

Karchmer, Raz, and Wigderson (1995) discuss the circuit depth complexity of n-bit Boolean functions constructed by composing up to d = log n/log log n levels of k = log n-bit Boolean functions. Any such function is in AC¹ . They conjecture that circuit depth is additive under composition, which would imply that any (bounded fan-in) circuit for this problem requires depth. This would separate AC¹ from NC¹. They recommend using the communication game characterization of circuit depth. In order to develop techniques for using communication complexity to prove circuit depth lower bounds, they suggest an intermediate communication complexity problem which they call the Universal Composition Relation. We give an almost optimal lower bound of dk—O(d ²(k log k)^1/2) for this problem. In addition, we present a proof, directly in terms of communication complexity, that there is a function on k bits requiring circuit depth. Although this fact can be easily established using a counting argument, we hope that the ideas in our proof will be incorporated more easily into subsequent arguments which use communication complexity to prove circuit depth bounds. Received: July 30, 1999.     

Approximate unions of lines and minkowski sums

We study the complexity of, and algorithms to construct, approximations of the union of lines and of the Minkowski sum of two simple polygons. We also studythick unions of lines and Minkowski sums, which are inflated with a small disc. Letb=D/ɛ be the ratio of the diameter of the region of interest and the maximum distance (or error) of the approximation. An approximate union of lines or Minkowski sum has complexity Θ (b ²) in the worst case. The thick union ofn lines has complexity Ω(n+b ²) andO(n +b√bn), and thick Minkowski sums have complexity Ω(n ²+b²) andO((n+b)n√blogn+n ² logn) in the worst case. We present algorithms that run inO(n+n ^2/3+δ b ^4/3 andO(min(bn,n ^4/3+δ b ^2/3)) time (any δ>0) for approximate and thick arrangements. For approximate Minkowski sums, the running time isO(min(b ² n,n ² +b ² + (nb)^4/3+δ); thick Minkowski sums takeO(n ^8/3+δ b ^2/3) time to compute.     

An O(n 3(log log n/log n)5/4) Time Algorithm for All Pairs Shortest Path

We present an O(n ³(log log n/log n)^5/4) time algorithm for all pairs shortest paths. This algorithm improves on the best previous result of O(n ³/log n) time. Research supported in part by NSF grant 0310245.     

Quantum Separation of Local Search and Fixed Point Computation

We give a lower bound of Ω(n ^(d−1)/2) on the quantum query complexity for finding a fixed point of a discrete Brouwer function over grid [n] ^d . Our lower bound is nearly tight, as Grover Search can be used to find a fixed point with O(n ^d/2) quantum queries. Our result establishes a nearly tight bound for the computation of d-dimensional approximate Brouwer fixed points defined by Scarf and by Hirsch, Papadimitriou, and Vavasis. It can be extended to the quantum model for Sperner’s Lemma in any dimensions: The quantum query complexity of finding a panchromatic cell in a Sperner coloring of a triangulation of a d-dimensional simplex with n ^d cells is Ω(n ^(d−1)/2). For d=2, this result improves the bound of Ω(n ^1/4) of Friedl, Ivanyos, Santha, and Verhoeven. More significantly, our result provides a quantum separation of local search and fixed point computation over [n] ^d , for d≥4. Aaronson’s local search algorithm for grid [n] ^d , using Aldous Sampling and Grover Search, makes O(n ^d/3) quantum queries. Thus, the quantum query model over [n] ^d for d≥4 strictly separates these two fundamental search problems.     

The prism machine: An alternative to the pyramid

The prism machine is a stack of n cellular arrays, each of size 2ⁿ × 2ⁿ. Cell (i, j) on level k is connected to cells (i, j), (i + 2^k, j), and (i, j + 2^k) on level k + 1, 1 ≤ k < n, where the sums are modulo 2ⁿ. Such a machine can perform various operations (e.g., “Gaussian” convolutions or least-squares polynomial fits) on image neighborhoods of power-of-2 sizes in every position in O(n) time, unlike a pyramid machine which can do this only in sampled positions. It can also compute the discrete Fourier transform in O(n) time. It consists of n · 4ⁿ cells, while a pyramid consists of fewer than 4ⁿ⁺¹/3 cells; but in practice n would be at most 10, so that a prism would be at most about seven times as large as a pyramid.     

The Dense k -Subgraph Problem

This paper considers the problem of computing the dense k -vertex subgraph of a given graph, namely, the subgraph with the most edges. An approximation algorithm is developed for the problem, with approximation ratio O(n ^δ ) , for some δ < 1/3 . Received April 29, 1997; revised June 26, 1998, and April 13, 1999.