On computing Boolean connectives of characteristic functions

This paper is a study of the existence of polynomial time Boolean connective functions for languages. A languageL has an AND function if there is a polynomial timef such thatf(x,y) L x L andy L. L has an OR function if there is a polynomial timeg such thatg(x,y) xL oryL. While all NP complete sets have these functions, Graph Isomorphism, which is probably not complete, is also shown to have both AND and OR functions. The results in this paper characterize the complete sets for the classes D^p and p^SAT[O(logn)] in terms of AND and OR and relate these functions to the structure of the Boolean hierarchy and the query hierarchies. Also, this paper shows that the complete sets for the levels of the Boolean hierarchy above the second level cannot have AND or OR unless the polynomial hierarchy collapses. Finally, most of the structural properties of the Boolean hierarchy and query hierarchies are shown to depend only on the existence of AND and OR functions for the NP complete sets.The first author was supported in part by NSF Research Grants DCR-8520597 and CCR-88-23053, and by an IBM Graduate Fellowship.     

Constructing sets of functions which have a givenF-cardinality

The termF-cardinality of (=F-card()) is introduced whereF: ^{n n} is a partial function and is a set of partial functionsf: ^{n n} . TheF-cardinality yields a lower bound for the worst-case complexity of computingF if only functionsf can be evaluated by the underlying abstract automaton without conditional jumps. This complexity bound isindependent from the oracles available for the abstract machine. Thus it is shown that any automaton which can only apply the four basic arithmetic operations needs (n logn) worst-case time to sortn numbers; this result is even true if conditional jumps witharbitrary conditions are possible. The main result of this paper is the following: Given a total functionF: ^{n n} and a natural numberk, it is almost always possible to construct a set such that itsF-cardinality has the valuek; in addition, can be required to be closed under composition of functionsf,g . Moreover, ifF is continuous, then consists of continuous functions.     

An Estimation Problem for Quasilinear Stochastic Partial Differential Equations

A problem of estimating a functional parameter (x) and functionals () based on observation of a solution u (t, x) of the stochastic partial differential equation is considered. The asymptotic problem setting, as the noise intensity 0, is investigated.     

A model of sequential computation with Pipelined access to memory

We introduce a new sequential model of computation, called the Logarithmic Pipelined Model (LPM), in which a RAM processor of fixed size has pipelined access to a memory ofm cells in time logm. Our motivation is that the usual assumption that a memory can be accessed in constant time becomes theoretically unacceptable asm increases, while an access time of logm is consistent with VLSI technologies. For a problem II of sizen, IT P, we denote byS(n) the time required by the fastest known sequential algorithm, and byT(n) the time required by the fastest algorithm solving II in the LPM. LettingO(logn) =O(logm), we define several complexity classes; in particular, LP₀ = {II P:T(n) =O(S(n))}, the class of problems for which the LPM is as efficient as the standard model, and LP =IIP:T(n) =O(S(n) logn), where the problems are less adequately solved in the new model. We first study the relations between the LPM and other models of computation. Of particular relevance is comparison with the PRAM model. Then we discuss several problems and derive the relative upper and lower bounds in the LPM. Our results lead to a new organization of parallel algorithms for list-linked structures.This work was supported in part by M.U.R.S.T. of Italy under a research grant.     

Finding a closest visible vertex pair between two polygons

Given nonintersecting simple polygonsP andQ, two verticespP andq Q are said to be visible if does not properly intersectP orQ. We present a parallel algorithm for finding a closest pair among all visible pairs (p,q),pP andqQ. The algorithm runs in time O(logn) using O(n) processors on a CREW PRAM, wheren=¦P¦+¦Q¦. This algorithm can be implemented serially in (n) time, which gives a new optimal sequential solution for this problem.This paper appeared in preliminary form as [1]. This work was supported in part by an AT&T BellLaboratories Graduate Fellowship, the Joint Services Electronics Program (U.S. Army, U.S. Navy, U.S. Air Force) under Contract N00014-90-J-1270, and NSF Grant CCR-89-22008. This work was done while the author was with the Department of Computer Science at the University of Illinois at Urbana-Champaign.     

Randomized range-maxima in nearly-constant parallel time

Given an array ofn input numbers, therange-maxima problem is that of preprocessing the data so that queries of the type what is the maximum value in subarray [i..j] can be answered quickly using one processor. We present a randomized preprocessing algorithm that runs inO(log^* n) time with high probability, using an optimal number of processors on a CRCW PRAM; each query can be processed in constant time by one processor. We also present a randomized algorithm for a parallel comparison model. Using an optimal number of processors, the preprocessing algorithm runs inO( (n)) time with high probability; each query can be processed inO ( (n)) time by one processor. (As is standard, (n) is the inverse of Ackermann function.) A constant time query can be achieved by some slowdown in the performance of the preprocessing stage.     

Pattern Matching for Sets of Segments

In this paper we present algorithms for a number of problems in geometric pattern matching where the input consists of a collection of orthogonal segments in the plane. Such collections arise naturally from problems in mapping buildings and robot exploration. We propose a new criterion for segment similarity called the coverage measure, and present efficient algorithms for maximizing it between sets of axis-parallel segments under translations. In the general case, we present a procedure running in time O(n³ log² n), and for the case when all segments are horizontal, we give a procedure that runs in time O(n² log² n). Here n is the number of segments. In addition, we show that an -approximation to the Hausdorff distance between two sets of horizontal segments under vertical translations can be computed in time O(n^3/2 max(poly(log M, log n, 1/))). Here, M denotes the ratio of the diameter to the closest pair of points in the sets of segments (where pairs of points lie on different segments). These algorithms are significant improvements over the general algorithm of Agarwal et al. that required time O(n⁴ log²     

Numerical stability of a convex hull algorithm for simple polygons

A numerically stable and optimalO(n)-time implementation of an algorithm for finding the convex hull of a simple polygon is presented. Stability is understood in the sense of a backward error analysis. A concept of the condition number of simple polygons and its impact on the performance of the algorithm is discussed. It is shown that if the condition number does not exceed (1+O())/(3), then, in floating-point arithmetic with the unit roundoff, the algorithm produces the vertices of a convex hull for slightly perturbed input points. The relative perturbation does not exceed 3(1+O()).J. W. Jaromczyk was partially supported by a grant from the Center for Robotics and Manufacturing Systems at the University of Kentucky and G. W. Wasilkowski was partially supported by the National Science Foundation under Grants CCR-89-05371 and CCR-91-14042.     

Quasi-optimal upper bounds for simplex range searching and new zone theorems

This paper presents quasi-optimal upper bounds for simplex range searching. The problem is to preprocess a setP ofn points in ^d so that, given any query simplexq, the points inP q can be counted or reported efficiently. Ifm units of storage are available (n <m <n ^d ), then we show that it is possible to answer any query inO(n ¹⁺/m ^1/d ) query time afterO(m ¹⁺) preprocessing. This bound, which holds on a RAM or a pointer machine, is almost tight. We also show how to achieveO(logn) query time at the expense ofO(n ^d+) storage for any fixed > 0. To fine-tune our results in the reporting case we also establish new zone theorems for arrangements and merged arrangements of planes in 3-space, which are of independent interest.A preliminary version of this paper has appeared in theProceedings of the Sixth Annual ACM Symposium on Computational Geometry, June 1990, pp. 23–33. Work on this paper by Bernard Chazelle has been supported by NSF Grant CCR-87-00917 and NSF Grant CCR-90-02352. Work on this paper by Micha Sharir has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grants DCR-83-20085 and CCR-8901484, and by grants from the U.S.-Israeli Binational Science Foundation, the NCRD—the Israeli National Council for Research and Development, and the Fund for Basic Research administered by the Israeli Academy of Sciences. Work by Emo Welzl has been supported by Deutsche Forschungsgemeinschaft Grant We 1265/1–2. Micha Sharir and Emo Welzl have also been supported by a grant from the German-Israeli Binational Science Foundation. Last but not least, all authors thank DIMACS, an NSF Science and Technology Center, for additional support under Grant STC-88-09648.     

Range Estimation Is NP-Hard for ε2 Accuracy and Feasible for ε2−δ

The basic problem of interval computations is: given a function f(x ₁,..., x _n) and n intervals [x _i, x _i], find the (interval) range yof the given function on the given intervals. It is known that even for quadratic polynomials f(x ₁,..., x _n), this problem is NP-hard. In this paper, following the advice of A. Neumaier, we analyze the complexity of asymptotic range estimation, when the bound on the width of the input intervals tends to 0. We show that for small c > 0, if we want to compute the range with an accuracy c ₂, then the problem is still NP-hard; on the other hand, for every > 0, there exists a feasible algorithm which asymptotically, estimates the range with an accuracy c ^2–.     

Robust algorithms for packet routing in a mesh

This paper considers the problem of permutation packet routing on a n×n mesh-connected array of processors. Each node in the array is assumed to be independently faulty with a probability bounded above by a valuep. This paper gives a routing algorithm which, ifp 0.29, will with very high probability route every packet that can be routed inO(n logn) steps with queue lengths that areO(log² n). Extensions to higher-dimensional meshes are given.     

Expansion in Terms of Power of a Small Parameter of the Maximum Rank Distribution of a Random Boolean Matrix

The paper considers an N × n matrix (N n) over a field GF(2) that consists of random values with a distribution depending on a small parameter . The expansion is found in terms of the power of the parameter of the probability that the matrix rank is equal to n. Exact values of the first three coefficients are indicated.     

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.     

Comparative complexity of the representation of languages by probabilistic automata

We analyze the effect of the degree of isolation of a cut point on the number of states P(U, ) of a probabilistic automaton representing the language U. We give an example of a language Uⁿ consisting of words of length n such that there exist numbers < for which P(Uⁿ, )/P(Uⁿ, )0 as n.Translated from Kibernetika, No. 3, pp. 21–25, May–June, 1989.     

Generalized Voronoi diagrams for a ladder: II. Efficient construction of the diagram

We present a collection of algorithms, all running in timeO(n ² logn (n) ^o((n)3)) for some fixed integers(where (n) is the inverse Ackermann's function), for constructing a skeleton representation of a suitably generalized Voronoi diagram for a ladder moving in a two-dimensional space bounded by polygonal barriers consisting ofn line segments. This diagram, which is a two-dimensional subcomplex of the dimensional configuration space of the ladder, is introduced and analyzed in a companion paper by the present authors. The construction of the diagram described in this paper yields a motion-planning algorithm for the ladder which runs within the same time bound given above.Work on this paper has been supported in part by Office of Naval Research Grant N00014-82-K-0381, and by grants from the Digital Equipment Corporation, the Sloan Foundation, the System Development Foundation, the IBM corporation, and by National Science Foundation CER Grant No. DCR-8320085. Work by the second author has also been supported in part by a grant from the US-Israeli Binational Science Foundation.     

On the Epsilon-entropy of One Class of Ellipsoids in a Hamming Space

The asymptotic behavior of the -entropy of ellipsoids in an n-dimensional Hamming space whose coefficients take only two different values is investigated as n . Explicit expressions for the main terms of the asymptotic expansion of -entropy of such ellipsoids are obtained under various relations between and parameters that define these ellipsoids.     

Left-noncounting languages

LetX be a finite alphabet and letX ^* be the free monoid generated byX. A languageA X ^* is called left-noncounting if there existsk 0 such that forx,y X ^*,x ^k y A if and only ifx ^k+i y A. The class of all left-noncounting languages overX forms a Boolean algebra which generally contains properly the class of all noncounting languages overX and is properly contained in the class of all power-separating languages overX. In this paper, we discuss some relations among these three classes of languages and we characterize the automata accepting the left-noncounting languages and the syn tactic monoids of the left-noncounting languages.This research has been supported by Grant A7877 of the National Research Council of Canada.     

ε-Entropy and Fractal Dimension of a State for a Gaussian Measure

Kolmogorov introduced the concept of -entropy to analyze information in classical continuous systems. The fractal dimension of a geometric set was introduced by Mandelbrot as a new criterion to analyze the geometric complexity of the set. The -entropy and the fractal dimension of a state in a general quantum system were introduced by one of the present authors (MO) in order to characterize chaotic properties of general states.In this paper, we show that -entropy of a state includes Kolmogorov's -entropy, and that the fractal dimension of a state describes fractal structure of Gaussian measures.     

On the oracle complexity of factoring integers

The problem of factoring integers in polynomial time with the help of an infinitely powerful oracle who answers arbitrary questions with yes or no is considered. The goal is to minimize the number of oracle questions. LetN be a given compositen-bit integer to be factored, wheren = log₂ N. The trivial method of asking for the bits of the smallest prime factor ofN requiresn/2 questions in the worst case. A non-trivial algorithm of Rivest and Shamir requires onlyn/3 questions for the special case whereN is the product of twon/2-bit primes. In this paper, a polynomial-time oracle factoring algorithm for general integers is presented which, for any >0, asks at most n oracle questions for sufficiently largeN, thus solving an open problem posed by Rivest and Shamir. Based on a plausible conjecture related to Lenstra's conjecture on the running time of the elliptic curve factoring algorithm, it is shown that the algorithm fails with probability at mostN ^–/2 for all sufficiently largeN.     

On parallel integer sorting

We present an optimal algorithm for sortingn integers in the range [1,n ^c ] (for any constantc) for the EREW PRAM model where the word length isn , for any >0. Using this algorithm, the best known upper bound for integer sorting on the (O(logn) word length) EREW PRAM model is improved. In addition, a novel parallel range reduction algorithm which results in a near optimal randomized integer sorting algorthm is presented. For the case when the keys are uniformly distributed integers in an arbitrary range, we give an algorithm whose expected running time is optimal.Supported by NSF-DCR-85-03251 and ONR contract N00014-87-K-0310