On the Convergence of Global Rational Approximants for Stochastic Discrete Event Systems

Difficulties often arise in analyzing stochastic discrete event systems due to the so-called curse of dimensionality. A typical example is the computation of some integer-parameterized functions, where the integer parameter represents the system size or dimension. Rational approximation approach has been introduced to tackle this type of computational complexity. The underline idea is to develop rational approximants with increasing orders which converge to the values of the systems. Various examples demonstrated the effectiveness of the approach. In this paper we investigate the convergence and convergence rates of the rational approximants. First, a convergence rate of order O(1/ ) is obtained for the so-called Type-1 rational approximant sequence. Secondly, we establish conditions under which the sequence of [n/n] Type-2 rational approximants has a convergence rate of order .     

Fast Range Searching with Delaunay Triangulations

This paper studies the idea of answering range searching queries using simple data structures. The only data structure we need is the Delaunay Triangulation of the input points. The idea is to first locate a vertex of the (arbitrary) query polygon and walk along the boundary of the polygon in the Delaunay Triangulation and report all the points enclosed by the query polygon. For a set of uniformly distributed random points in 2-D and a query polygon the expected query time of this algorithm is O(n ^1/3 + Q + E K + L _r n ^1/2), where Q is the size of the query polygon , {\bf E}K = O(n\bcdot area is the expected number of output points, L _r is a parameter related to the shape of the query polygon and n, and L _r is always bounded by the sum of the edge lengths of . Theoretically, when L _r = O(1/n^1/6) the expected query time is O(n^1/3 + Q + E K), which improves the best known average query time for general range searching. Besides the theoretical meaning, the good property of this algorithm is that once the Delaunay Triangulation is given, no additional preprocessing is needed. In order to obtain empirical results, we design a new algorithm for generating random simple polygons within a given domain. Our empirical results show that the constant coefficient of the algorithm is small, at least for the special (practical) cases when the query polygon is either a triangle (simplex range searching) or an axis-parallel box (orthogonal range searching) and for the general case when the query polygons are generated by our new polygon-generating algorithms and their sizes are relatively small.     

On the rank of certain finite fields

In the present paper we shall show that the rank of the finite field regarded as an -algebra has one of the two values 2n or 2n+1 ifn satisfies 1/2q+1<n<1/2(m(q)–2). Herem(q) denotes the maximum number of -rational points of an algebraic curve of genus 2 over . Using results of Davenport-Hasse, Honda and Rück we shall give lower bounds form(q) which are close to the Hasse-Weil bound . For specialq we shall further show thatm(q) is equal to the Hasse-Weil bound.     

Quantum Algorithms for Matching Problems

We present quantum algorithms for the following matching problems in unweighted and weighted graphs with n vertices and m edges:

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.     

Distributed MST for constant diameter graphs

This paper considers the problem of distributively constructing a minimum-weight spanning tree (MST) for graphs of constant diameter in the bounded-messages model, where each message can contain at most B bits for some parameter B. It is shown that the number of communication rounds necessary to compute an MST for graphs of diameter 4 or 3 can be as high as and , respectively. The asymptotic lower bounds hold for randomized algorithms as well. On the other hand, we observe that O(log n) communication rounds always suffice to compute an MST deterministically for graphs with diameter 2, when B = O(log n). These results complement a previously known lower bound of for graphs of diameter Ω(log n). An extended abstract of this work appears in Proceedings of 20th ACM Symposium on Principles of Distributed Computing, August 2001.     

Representing Boolean functions as polynomials modulo composite numbers

Define the MOD _m -degree of a boolean functionF to be the smallest degree of any polynomialP, over the ring of integers modulom, such that for all 0–1 assignments , iff . We obtain the unexpected result that the MOD _m -degree of the OR ofN variables is , wherer is the number of distinct prime factors ofm. This is optimal in the case of representation by symmetric polynomials. The MOD _n function is 0 if the number of input ones is a multiple ofn and is one otherwise. We show that the MOD _m -degree of both the MOD _n and functions isN ⁽¹⁾ exactly when there is a prime dividingn but notm. The MOD _m -degree of the MOD _m function is 1; we show that the MOD _m -degree of isN ⁽¹⁾ ifm is not a power of a prime,O(1) otherwise. A corollary is that there exists an oracle relative to which the MOD _m P classes (such as P) have this structure: MOD _m P is closed under complementation and union iffm is a prime power, and MOD _n P is a subset of MOD _m P iff all primes dividingn also dividem.     

Solution of Systems of Linear Equations by the p-Adic Method

A new algorithm for solving systems of linear equations Ax = b in an Euclidean domain is suggested. In the case of the ring of integers, the complexity of this algorithm is O (n ³ mlog² ||A||), where n)$$ " align="middle" border="0"> is a matrix of rank n and , if standard algorithms for the multiplication of integers and matrices are used. Under the same conditions, the best algorithm of this kind among those published earlier, which was suggested by Labahn and Storjohann in [1], has complexity O (n ⁴ mlog² ||A||). True, when using fast algorithms for the multiplication of numbers and matrices, the theoretical complexity estimate for the latter algorithm is O (n mlog² ||A||), which is better than the similar estimate O (n ³ mlog||A||) for the new algorithm.     

Improved Bounds on Quantum Learning Algorithms

In this article we give several new results on the complexity of algorithms that learn Boolean functions from quantum queries and quantum examples.

On the hardness of computing the permanent of random matrices

Extending a line of research initiated by Lipton, we study the complexity of computing the permanent of randomn byn matrices with integer values between 0 andp–1, for any suitably large primep. Previous to our work, it was shown hard to compute the permanent of half these matrices (by Gemmell and Sudan), and to enumerate for any matrix a polynomial number of options for its permanent (by Cai and Hemachandra, and by Toda). We show that unless the polynomial-time hierarchy collapses to its second level, no polynomial time algorithm can compute the permanent of every matrix with probability at least 13n ³/p, nor can it compute the permanent of at least a -fraction of the matrices. Asp may be expenential inn, these represent very low success probabilities for any efficient algorithm that attempts to compute the permanent. For 0/1 matrices, our results show that their permanents cannot be guessed with probability greater than .We also show that it is hard to get even partial information about the value of the permanent modulop. For random matrices we show that any balanced polynomial-time 0/1 predicate (e.g., the least significant bit, the parity of all the bits, the quadratic residuosity character) cannot be guessed with probability significantly greater than 1/2 (unless the polynomial-time hierarchy collapses). This result extends to showing simultaneous hardness for linear size groups of bits.     

Rangierkomplexität von permutationen

Summary We define a measure of complexity for (the group of permutations ofn elements). We thus obtain non trivial lower bounds for the number of Turing steps necessary for applaying a permutation to a tape withn entries. Transposing annxn matrix, for example, stored linearly needs at leastCn ² Ign steps.     

Branching processes in the analysis of the heights of trees

Summary It is shown how the theory of branching processes can be applied in the analysis of the expected height of random trees. In particular, we will study the height of random binary search trees, random k—d trees, quadtrees and union-find trees under various models of randomization. For example, for the random binary search tree constructed from a random permutation of 1,..., n, it is shown that H _n/(c log(n)) tends to 1 in probability and in the mean as n, where H _n is the height of the tree, and c =4.31107... is a solution of the equation . In addition, we show that in probability.Research of the author was sponsored by NSERC Grant A3456 and by FCAC Grant EQ-1678     

Parallel Self-Index Integer Sorting

We consider the problem of sorting n integers when the elements are drawn from the restricted domain [1...n]. A new deterministic parallel algorithm for sorting n integers is obtained. Its running time is O(lognlog(n/logn)) using n/logn processors on EREW (exclusive read exclusive write) PRAM (parallel random access machine). Also, our algorithm was modified to become optimal when we use processors. This algorithm belongs to class EP (Efficient, Polynomial fast).     

The computational complexity of recognizing permutation functions

Let be a finite field withq elements and a rational function over . No polynomial-time deterministic algorithm is known for the problem of deciding whetherf induces a permutation on . The problem has been shown to be in co-R co-NP, and in this paper we prove that it is inR NP and hence inZPP, and it is deterministic polynomial-time reducible to the problem of factoring univariate polynomials over . Besides the problem of recognizing prime numbers, it seems to be the only natural decision problem inZPP unknown to be inP. A deterministic test and a simple probabilistic test for permutation functions are also presented.     

Low-randomness constant-round private XOR computations

In this paper we study the randomness complexity needed to distributively perform k XOR computations in a t-private way using constant-round protocols in the case in which the players are honest but curious. We show that the existence of a particular family of subsets allows the recycling of random bits for constant-round private protocols. More precisely, we show that after a 1-round initialization phase during which random bits are distributed among n players, it is possible to perform each of the k XOR computations using two rounds of communication. For , for any c < 1/2, we design a protocol that uses O(kt ²log n) random bits.     

Representation of ℤ<Subscript>4</Subscript>-Linear Preparata Codes Using Vector Fields

A binary code is called ℤ₄-linear if its quaternary Gray map preimage is linear. We show that the set of all quaternary linear Preparata codes of length n = 2^m, m odd, m ≥ 3, is nothing more than the set of codes of the form with

Three-dimensional graph drawing

Graph drawing research has been mostly oriented toward two-dimensional drawings. This paper describes an investigation of fundamental aspects of three-dimensional graph drawing. In particular we give three results concerning the space required for three-dimensional drawings. We show how to produce a grid drawing of an arbitraryn-vertex graph with all vertices located at integer grid points, in ann×2n×2n grid, such that no pair of edges cross. This grid size is optimal to within a constant. We also show how to convert an orthogonal two-dimensional drawing in anH×V integer grid to a three-dimensional drawing with volume. Using this technique we show, for example, that three-dimensional drawings of binary trees can be computed with volume . We give an algorithm for producing drawings of rooted trees in which thez-coordinate of a node represents the depth of the node in the tree; our algorithm minimizes thefootprint of the drawing, that is, the size of the projection in thexy plane. Finally, we list significant unsolved problems in algorithms for three-dimensional graph drawing. This work was performed as part of the Information Visualization Group(IVG) at the University of Newcastle. The IVG is supported in part by IBM Toronto Laboratory.     

On the complexity of distributed stable matching with small messages

We consider the distributed complexity of the stable matching problem (a.k.a. “stable marriage”). In this problem, the communication graph is undirected and bipartite, and each node ranks its neighbors. Given a matching of the nodes, a pair of unmatched nodes is called blocking if they prefer each other to their assigned match. A matching is called stable if it does not induce any blocking pair. In the distributed model, nodes exchange messages in each round over the communication links, until they find a stable matching. We show that if messages may contain at most B bits each, then any distributed algorithm that solves the stable matching problem requires ${\Omega(\sqrt{n/B\log n})}We consider the distributed complexity of the stable matching problem (a.k.a. “stable marriage”). In this problem, the communication graph is undirected and bipartite, and each node ranks its neighbors. Given a matching of the nodes, a pair of unmatched nodes is called blocking if they prefer each other to their assigned match. A matching is called stable if it does not induce any blocking pair. In the distributed model, nodes exchange messages in each round over the communication links, until they find a stable matching. We show that if messages may contain at most B bits each, then any distributed algorithm that solves the stable matching problem requires W(?{n/Blogn}){\Omega(\sqrt{n/B\log n})} communication rounds in the worst case, even for graphs of diameter O(log n), where n is the number of nodes in the graph. Furthermore, the lower bound holds even if we allow the output to contain O(?n){O(\sqrt n)} blocking pairs, and if a pair is considered blocking only if they like each other much more then their assigned match.     

Exact optimal grillage layouts — Part I: Combinations of free and simply supported edges

In the first instalment of this three-part study, a comprehensive treatment of analytically derived, exact optimal grillage layouts for combinations of simply supported and free edges is given. In part two, grillages with combinations of simply supported, clamped and free edges will be considered.Notation k constant in specific cost function - M beam bending moment - r radius of circular edge - R ⁺,R ^–,S ⁺,S ^–,T optimal regions - x, x _j coordinate along a beam (j) - slope of the adjoint deflection at pointD in directionDA - t, v coordinates along the free edge - adjoint deflection - angle between long beams and free edge - angle between free and simply supported edges - curvature of the adjoint deflection - , angles for layouts with circular edge - total weight (cost) of grillage - coordinate along a beam in anR ⁺ region - distance defined in Fig. 3