A Delay-Averaged Logistic Model

For the equation x(t) = x(t) (1-(1/) _t-- ^t- x(u)du), > 0, > 0, > 0, conditions for the stability of a nonzero stationary solution under small perturbations are determined.     

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.     

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.     

ε-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.     

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.     

Computational complexity of one-step methods for a scalar autonomous differential equation

The problem is to calculate an approximate solution of an initial value problem for a scalar autonomous differential equation. A generalized notion of a nonlinear Runge-Kutta (NRK) method is defined. We show that the order of anys-stage NRK method cannot exceed 2s–1; hence, the family of NRK methods due to Brent has the maximal order possible. Using this result, we derive complexity bounds on the problem of finding an approximate solution with error not exceeding . We also compute the order which minimizes these bounds, and show that this optimal order increases as decreases, tending to infinity as tends to zero.

---

Rechnerische Komplexität von Ein-Schritt-Verfahren für eine skalare autonome Differentialgleichung

Zusammenfassung Es wird das Problem behandelt, die Näherungslösung für ein Anfangswertproblem für eine skalare autonome Differentialgleichung abzuschätzen. Eine Verallgemeinerung eines nichtlinearen Runge-Kutta-(NRK-) Verfahrens wird definiert. Es wird gezeigt, daß die Ordnung irgendeiners-wertigen NRK-Methode nicht größer als 2s–1 sein kann; deshalb hat die Familie der NRK-Verfahren von Brent die maximale mögliche Ordnung. Unter Benutzung dieser Resultate werden Schranken angegeben zum Problem des Auffindens von Näherungslösungen, deren Fehler nicht größer als ist. Es wird ebenfalls die Ordnung berechnet, welche die Schranken minimiert, und es wird gezeigt, daß die optimale Ordnung wächst, falls abnimmt; sie geht nach unendlich, wenn gegen Null geht.

---

---

This research was supported in part by the National Science Foundation under Grant MCS75-222-55 and the Office of Naval Research under Contract N00014-76-C-0370 NR 044-422     

Approximation Schemes for Degree-Restricted MST and Red–Blue Separation Problems

We develop a quasi-polynomial time approximation scheme for the Euclidean version of the Degree-Restricted MST Problem by adapting techniques used previously by Arora for approximating TSP. Given n points in the plane, d = 3 or 4, and > 0, the scheme finds an approximation with cost within 1 + of the lowest cost spanning tree with the property that all nodes have degree at most d. We also develop a polynomial time approximation scheme for the Euclidean version of the Red–Blue Separation Problem, again extending Aroras techniques. Given > 0, the scheme finds an approximation with cost within 1+ of the cost of the optimum separating polygon of the input nodes, in nearly linear time.     

Clock synchronization and the power of broadcasting

Summary We investigate the power of a broadcast mechanism in a distributed network. We do so by considering the problem of synchronizing clocks in an errorfree network, under the assumption that there is no upper bound on message transmission time, but that broadcast messages are guaranteed to be received within an interval of size , for some fixed constant . This is intended to be an idealization of what happens in multiple access networks, such as the Ethernet. We then consider tradeoffs between the type and number of broadcasts, and the tightness of synchronization. Our results include (1) matching upper and lower bounds of (1+1/K) on the precision of clock synchronization attainable forn3 process usingK (n–1)-casts, 3Kn, (2) matching upper and lower bounds of (1+1/n) on the precision of clock synchronization attainable forn3 processes using an arbitrary number of (n–1)-casts, and (3) matching upper and lower bounds of (1+n–2/n) on the precision attainable using 2-casting. Joseph Y. Halpern received a B.Sc. in mathematics from the University of Toronto in 1975, and a Ph.D. in mathematics from Harvard University in 1981. In between, he spent two years as the head of the Mathematics Department at Bawku Secondary School in Ghara. After a year as a visiting scientist at MIT, he joined IBM in 1982, where he is currently a research staff member, as well as being a consulting professor at Stanford University. He was manager of the mathematics and related computer sience department at IBM from 1987–1989. He was program chairman and organizer of the first conference on Theoretical Aspects of Reasoning About Knowledge in 1986, program chairman of the 1986 ACM Symposium on Principles of Distributed Computing and of the 1991 ACM Symposium on Theory of Computing. He was recipent (together with Ron Fagin) of the MIT Publisher's Prize for best paper at the 1985 International Joint Conference on Artificial Intelligence and again winner of the Publisher's Prize at the 1989 International Joint Conference on Artificial Intelligence. Ichiro Suzuki is an Associate Professor of Computer Science at the University of Wisconsin-Milwaukee. He received a D.E. degree in information and computer sciences from Osaka University, Japan, in 1983. His major research interests are distributed systems and computational geometry.This author was supported in part by the National Science Foundation under grant CCR-9004346     

Improving known solutions is hard

In this paper, we study the complexity of computing better solutions to optimization problems given other solutions. We use a model of computation suitable for this purpose, the counterexample computation model. We first prove that, if PH _P ³ , polynomial time transducers cannot compute optimal solutions for many problems, even givenn ^1– non-trivial solutions, for any >0. These results are then used to establish sharp lower bounds for several problems in the counterexample model. We extend the model by defining probabilistic counterexample computations and show that our results hold even in the presence of randomness.     

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.     

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.     

Efficient PRAM simulation on a distributed memory machine

We present algorithms for the randomized simulation of a shared memory machine (PRAM) on a Distributed Memory Machine (DMM). In a PRAM, memory conflicts occur only through concurrent access to the same cell, whereas the memory of a DMM is divided into modules, one for each processor, and concurrent accesses to the same module create a conflict. Thedelay of a simulation is the time needed to simulate a parallel memory access of the PRAM. Any general simulation of anm processor PRAM on ann processor DMM will necessarily have delay at leastm/n. A randomized simulation is calledtime-processor optimal if the delay isO(m/n) with high probability. Using a novel simulation scheme based on hashing we obtain a time-processor optimal simulation with delayO(log log(n) log*(n)). The best previous simulations use a simpler scheme based on hashing and have much larger delay: (log(n)/log log(n)) for the simulation of an n processor PRAM on ann processor DMM, and (log(n)) in the case where the simulation is time-processor optimal.Our simulations use several (two or three) hash functions to distribute the shared memory among the memory modules of the PRAM. The stochastic processes modeling the behavior of our algorithms and their analyses based on powerful classes of universal hash functions may be of independent interest.Research partially supported by NSF/DARPA Grant CCR-9005448. Work was done while at the University of California at Berkeley and the International Computer Science Institute, Berkeley, CA.Research partially supported by National Science Foundation Operating Grant CCR-9016468, National Science Foundation Operating Grant CCR-9304722, United States-Israel Binational Science Foundation Grant No. 89-00312, United States-Israel Binational Science Foundation Grant No. 92-00226, and ESPRIT BR Grant EC-US 030.Part of work was done during a visit at the International Computer Science Institute at Berkeley; supported in part by DFG-Forschergruppe Effiziente Nutzung massiv paralleler Systeme, Teilprojekt 4, and by the Esprit Basic Research Action Nr. 7141 (ALCOM II).     

Separating complexity classes related to bounded alternating ω-branching programs

We develop a theory of communication within branching programs that provides exponential lower bounds on the size of branching programs that are bounded alternating. Our theory is based on the algebraic concept of -branching programs, : , a semiring homomorphism, that generalizes ordinary branching programs, -branching programs [M2] andMOD _p-branching programs [DKMW].Due to certain exponential lower and polynomial upper bounds on the size of bounded alternating -branching programs we are able to separate the corresponding complexity classesN _ba ,co-N _{ba ba} , andMOD _p - _ba ,p prime, from each other, and from that classes corresponding to oblivious linear length-bounded branching programs investigated in the past.     

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.     

Unextendible Product Bases and Locally Unconvertible Bound Entangled States

Mutual convertibility of bound entangled states under local quantum operations and classical communication (LOCC) is studied. We focus on states associated with unextendible product bases (UPB) in a system of three qubits. A complete classification of such UPBs is suggested. We prove that for any pair of UPBs S and T the associated bound entangled states _S and _T cannot be converted to each other by LOCC, unless S and T coincide up to local unitaries. More specifically, there exists a finite precision (S,T) > 0 such that for any LOCC protocol mapping _S into a probabilistic ensemble (p, ), the fidelity between _T and any possible final state satisfies F(_T, ) = 1 - (S,T).PACS: 03.65.Bz; 03.67.-a; 89.70+c.     

Scheduling Malleable Parallel Tasks: An Asymptotic Fully Polynomial Time Approximation Scheme

A malleable parallel task is one whose execution time is a function of the number of (identical) processors allotted to it. We study the problem of scheduling a set of n independent malleable tasks on an arbitrary number m of parallel processors and propose an asymptotic fully polynomial time approximation scheme. For any fixed > 0, the algorithm computes a non-preemptive schedule of length at most (1+) times the optimum (plus an additive term) and has running time polynomial in n,m and 1 /.     

Space Efficient Hash Tables with Worst Case Constant Access Time

We generalize Cuckoo Hashing to d-ary Cuckoo Hashing and show how this yields a simple hash table data structure that stores n elements in (1 + )n memory cells, for any constant > 0. Assuming uniform hashing, accessing or deleting table entries takes at most d=O (ln (1/)) probes and the expected amortized insertion time is constant. This is the first dictionary that has worst case constant access time and expected constant update time, works with (1 + )n space, and supports satellite information. Experiments indicate that d = 4 probes suffice for 0.03. We also describe variants of the data structure that allow the use of hash functions that can be evaluated in constant time.     

Path Integration on a Quantum Computer

We study path integration on a quantum computer that performs quantum summation. We assume that the measure of path integration is Gaussian, with the eigenvalues of its covariance operator of order j^-k with k>1. For the Wiener measure occurring in many applications we have k=2. We want to compute an -approximation to path integrals whose integrands are at least Lipschitz. We prove: Path integration on a quantum computer is tractable. Path integration on a quantum computer can be solved roughly ^-1 times faster than on a classical computer using randomization, and exponentially faster than on a classical computer with a worst case assurance. The number of quantum queries needed to solve path integration is roughly the square root of the number of function values needed on a classical computer using randomization. More precisely, the number of quantum queries is at most 4.46 ^-1. Furthermore, a lower bound is obtained for the minimal number of quantum queries which shows that this bound cannot be significantly improved. The number of qubits is polynomial in ^-1. Furthermore, for the Wiener measure the degree is 2 for Lipschitz functions, and the degree is 1 for smoother integrands. PACS: 03.67.Lx; 31.15Kb; 31.15.-p; 02.70.-c     

Efficient emulation of single-hop radio network with collision detection on multi-hop radio network with no collision detection

Summary This paper presents an efficient randomized emulation ofsingle-hop radio networkwith collision detection onmulti-hop radio networkwithout collision detection. Each step of the single-hop network is emulated by rounds of the multi-hop network and succeeds with probability 1–. (n is the number of processors,D the diameter and the maximum degree). It is shown how to emulate any polynomial algorithm such that the probability of failure remains . A consequence of the emulation is an efficient randomized algorithm for choosing a leader in a multi-hop network. Reuven Bar-Yehuda was born in Iran, on July 17th 1951. Received B.A., M.Sc., and D.Sc. in Computer Science from the Technion — Israel Institute of Technology, Haifa, Israel, in 1978, 1980, and 1983, respectively. He is currently a Senior Lecturer of Computer Science at the Technion. From 1984 to 1986, he was a visiting assistant professor in the Computer Science Dept. at the Duke Univesity His research interests include computational geometry, VLSI, graph algorithms and distributed algorithms. Oded Goldreich was born in Tel-Aviv, Israel, on February 4th 1957. Received B.A., M.Sc., and D.Sc. in Computer Science from the Technion — Israel Institute of Technology, Haifa, Israel, in 1980, 1982, and 1983, respectively. He is currently an Associate Professor of Computer Science at the Technion. From 1983 to 1986, he was a postdoctoral fellow at MIT's Laboratory for Computer Science. His research interests include cryptography and related areas, relation between randomness and algorithms, and distributed computation. Alon Itai was born in Scotland, on December 12th 1946. Received B.Sc. in Mathematics from the Hebrew University in Jerusalem in 1969. M.Sc., and Ph.D. in Computer Science from the Weizmann Institute of Science, Rehovot, Israel in 1971 and 1976. He is currently an Associate Professor of Computer Science at the Technion. His research interests include randomized and distributed algorithms, computational learning theory and performance evaluation.The second author was partially supported by grant No. 86-00301 from the United States—Israel Bi-national Science Foundation BSF), Jerusalem, Israel.     

Diagrammatic Analysis of Interval Linear Equations - Part II: The Two-Dimensional Case and Generalization to n Dimensions

Using the results obtained for the one-dimensional case in Part I (Reliable Computing 9(1) (2003), pp. 1–20) of the paper, an analysis of the two-dimensional relational expression a ₁ x ₁ + a ₂ x ₂ b, where {, , , =}, is conducted with the help of a midpoint-radius diagram and other auxiliary diagrams. The solution sets are obtained with a simple boundary-line selection rule derived using these tools, and are characterized by types of one-dimensional cuts through the solution space. A classification of basic possible solution types is provided in detail. The generalization of the approach for n-dimensional interval systems and avenues for further research are also outlined.