On selecting thek largest with median tests

LetW _itk(n) be the minimax complexity of selecting thek largest elements ofn numbersx ₁,x ₂,...,x _n by pairwise comparisonsx _i :x _j . It is well known thatW ₂(n) =n–2+ [lgn], andW _k (n) = n + (k–1)lg n +O(1) for all fixed k 3. In this paper we studyW _k (n), the minimax complexity of selecting thek largest, when tests of the form Isx _i the median of {x _i ,x _j ,x _t }? are also allowed. It is proved thatW₂(n) =n–2+ [lgn], andW _k (n) =n + (k–1)lg₂ n +O(1) for all fixedk3.This research was supported in part by the National Science Foundation under Grant No. DCR-8308109.     

Calculation of coordinates from molecular geometric parameters and the concept of a geometric calculator

Three different geometric parameters, distance r(i,j), angle θ(i,j, k), and dihedral (or torsion) angle φ(i,j, k, l), are commonly used to specify the shape of a molecule. Given Cartesian coordinates it is simple to calculate such parameters. The, non-trivial, inverse problem of finding coordinates when given such parameters is considered here. When a triple of such geometric parameters is given to specify the position of an atom, n, relative to reference atoms i,j, k,…, with known positions, five qualitatively different cases arise: r(n, i), θ(n, i,j), φ(n, i,j, k), θ(j, n, i) and φ(k, n, i,j). Each such geometric coordinate specifies n to lie on a certain type of surface. To calculate its position one must find the point of intersection of three such surfaces. A program, Evclid, that can perform these calculations is integrated with an interactive set of routines that constitute a geometric calculator and editor. It works on (three-dimensional) points and has a number of input, display and output options. It can translate, rotate, reflect, invert and scale as well as edit the point set or subsets.     

Systems of Strings with High Mutual Complexity

Consider a binary string x ₀ of Kolmogorov complexity K(x ₀) n. The question is whether there exist two strings x ₁ and x ₂ such that the approximate equalities K(x _i x _j ) n and K(x _i x _j , x _k ) n hold for all 0 i, j, k 2, i j k, i k. We prove that the answer is positive if we require the equalities to hold up to an additive term O(log K(x ₀)). It becomes negative in the case of better accuracy, namely, O(log n).     

On selecting thek largest with median tests

LetW _itk(n) be the minimax complexity of selecting thek largest elements ofn numbersx ₁,x ₂,...,x _n by pairwise comparisonsx _i :x _j . It is well known thatW ₂(n) =n?2+ [lgn], andW _k (n) = n + (k?1)lg n +O(1) for all fixed k ≥ 3. In this paper we studyW′ _k (n), the minimax complexity of selecting thek largest, when tests of the form “Isx _i the median of {x _i ,x _j ,x _t }?” are also allowed. It is proved thatW′₂(n) =n?2+ [lgn], andW′ _k (n) =n + (k?1)lg₂ n +O(1) for all fixedk≥3.     

Calculating optimal addition chains

An addition chain is a finite sequence of positive integers 1 = a ₀ ≤ a ₁ ≤ · · · ≤ a _r = n with the property that for all i > 0 there exists a j, k with a _i = a _j + a _k and r ≥ i > j ≥ k ≥ 0. An optimal addition chain is one of shortest possible length r denoted l(n). A new algorithm for calculating optimal addition chains is described. This algorithm is far faster than the best known methods when used to calculate ranges of optimal addition chains. When used for single values the algorithm is slower than the best known methods but does not require the use of tables of pre-computed values. Hence it is suitable for calculating optimal addition chains for point values above currently calculated chain limits. The lengths of all optimal addition chains for n ≤ 2³² were calculated and the conjecture that l(2n) ≥ l(n) was disproved. Exact equality in the Scholz–Brauer conjecture l(2 ⁿ − 1) = l(n) + n − 1 was confirmed for many new values.     

Panconnectivity of Cartesian product graphs

A graph G of order n (≥2) is said to be panconnected if for each pair (x,y) of vertices of G there exists an xy-path of length ℓ for each ℓ such that d _G (x,y)≤ℓ≤n−1, where d _G (x,y) denotes the length of a shortest xy-path in G. In this paper, we consider the panconnectivity of Cartesian product graphs. As a consequence of our results, we prove that the n-dimensional generalized hypercube Q _n (k ₁,k ₂,…,k _n ) is panconnected if and only if k _i ≥3 (i=1,…,n), which generalizes a result of Hsieh et al. that the 3-ary n-cube Q³_nQ^{3}_{n} is panconnected.     

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.     

Fast Algorithms for the Density Finding Problem

We study the problem of finding a specific density subsequence of a sequence arising from the analysis of biomolecular sequences. Given a sequence A=(a ₁,w ₁),(a ₂,w ₂),…,(a _n ,w _n ) of n ordered pairs (a _i ,w _i ) of numbers a _i and width w _i >0 for each 1≤i≤n, two nonnegative numbers ℓ, u with ℓ≤u and a number δ, the Density Finding Problem is to find the consecutive subsequence A(i ^*,j ^*) over all O(n ²) consecutive subsequences A(i,j) with width constraint satisfying ℓ≤w(i,j)=∑ _r=i ^j w _r ≤u such that its density is closest to δ. The extensively studied Maximum-Density Segment Problem is a special case of the Density Finding Problem with δ=∞. We show that the Density Finding Problem has a lower bound Ω(nlog n) in the algebraic decision tree model of computation. We give an algorithm for the Density Finding Problem that runs in optimal O(nlog n) time and O(nlog n) space for the case when there is no upper bound on the width of the sequence, i.e., u=w(1,n). For the general case, we give an algorithm that runs in O(nlog ² m) time and O(n+mlog m) space, where and w _min=min  _r=1 ⁿ w _r . As a byproduct, we give another O(n) time and space algorithm for the Maximum-Density Segment Problem. Grants NSC95-2221-E-001-016-MY3, NSC-94-2422-H-001-0001, and NSC-95-2752-E-002-005-PAE, and by the Taiwan Information Security Center (TWISC) under the Grants NSC NSC95-2218-E-001-001, NSC95-3114-P-001-002-Y, NSC94-3114-P-001-003-Y and NSC 94-3114-P-011-001.     

Improved Generation of Minimal Addition Chains

An addition chain for a natural number n is a sequence 1=a ₀<a ₁< . . . <a _r =n of numbers such that for each 0<i≤r, a _i =a _j +a _k for some 0≤k≤j<i. An improvement by a factor of 2 in the generation of all minimal (or one) addition chains is achieved by finding sufficient conditions for star steps, computing what we will call nonstar lower bound in a minimal addition and omitting the sorting step.     

Finding the Extrema of a Distributed Multiset

We consider the problem of finding the extrema of a distributed multiset in a ring, that is, of determining the minimum and the maximum values,x_minandx_max, of a multisetX= {x₀,x₂, ...,x_n−1} whose elements are drawn from a totally ordered universeUand stored at thenentities of a ring network. This problem is unsolvable if the ring size is not known to the entities, and it has complexity Θ(n²) in the case of asynchronous rings of known size. We show that, in synchronous rings of known size, this problem can always be solved inO((c+ logn) ·n) bits andO(n·c·x^1/c) time for any integerc> 0, wherex= Max{|x_min|, |x_max|}. The previous solutions requiredO(n²) bits and the same amount of time. Based on these results, we also present a bit-optimal solution to the problem of finding the multiplicity of the extrema.     

Output-Sensitive Algorithm for Computing β-Skeletons

The β-skeleton is a measure of the internal shape of a planar set of points. We get an entire spectrum of shapes by varying the parameter β. For a fixed value of β, a β-skeleton is a geometric graph obtained by joining each pair of points whose β-neighborhood is empty. For β≥1, this neighborhood of a pair of points p _i ,p _j is the interior of the intersection of two circles of radius , centered at the points (1−β/2)p _i +(β/2)p _j and (β/2)p _i +(1−β/2)p _j , respectively. For β∈(0,1], it is the interior of the intersection of two circles of radius , passing through p _i and p _j . In this paper we present an output-sensitive algorithm for computing a β-skeleton in the metrics l ₁ and l _∞ for any β≥2. This algorithm is in O(nlogn+k), where k is size of the output graph. The complexity of the previous best known algorithm is in O(n ^5/2logn) [7]. Received April 26, 2000     

Exponential lower bounds for depth three Boolean circuits

We consider the class of unbounded fan-in depth three Boolean circuits, for which the bottom fan-in is limited by k and the top gate is an OR. It is known that the smallest such circuit computing the parity function has gates (for k = O(n ^1/2)) for some , and this was the best lower bound known for explicit (P-time computable) functions. In this paper, for k = 2, we exhibit functions in uniform NC ¹ that require size depth 3 circuits. The main tool is a theorem that shows that any circuit on n variables that accepts a inputs and has size s must be constant on a projection (subset defined by equations of the form x _i = 0, x _i = 1, x _i = x _j or x _i = ) of dimension at least log(a/s)log n. Received: April 1, 1997.     

Fast algorithms for minimum matrix norm with application in computer graphics

In this paper we consider the following problem. Given (r ₁,r ₂, ...,r _n) R ⁿ, for anyI= (I ₁,I ₂,...,I _n) Z ⁿ, letE ₁=(e _ij), wheree _ij=(r _i–r_j)–(I _i–I_j), findI Z ⁿ such that |E _I| is minimized, where |·| is a matrix norm. This problem arises from optimal curve rasterization in computer graphics, where minimum distortion of curve dynamic context is sought. Until now, there has been no polynomial-time solution to this computer graphics problem. We present a very simpleO(n lgn)-time algorithm to solve this problem under various matrix norms.This research was supported by the Natural Sciences and Engineering Research Council of Canada under Grant OGP0046373.     

Fitting a least squares piecewise linear continuous curve in two dimensions

An optimal piecewise linear continuous fit to a given set of n data points D = {(x_i, y_i) : 1 ≤ i ≤ n} in two dimensions consists of a continuous curve defined by k linear segments {L₁, L₂,…,L_k} which minimizes a weighted least squares error function with weight w_i at (x_i, y_i), where k ≥ 1 is a given integer. A key difficulty here is the fact that the linear segment L_j, which approximates a subset of consecutive data points D_j ⊂ D in an optimal solution, is not necessarily an optimal fit in itself for the points D_j. We solve the problem for the special case k = 2 by showing that an optimal solution essentially consists of two least squares linear regression lines in which the weight w_j of some data point (x_j, y_j) is split into the weights λw_j and (1 − λ)w_j, 0 ≤ λ ≤ 1, for computations of these lines. This gives an algorithm of worst-case complexity O(n) for finding an optimal solution for the case k = 2.     

Characterization of normal forms possessing inverse in the λ-β-η-calculus

The aim of this paper is to generalize a result given by Curry and Feys, who have shown that the only regular combinators possessing inverse in the λ-β-η-calculus are the permutators, whose definition is p=λzλx₁…λx_n(zx_i1…x_in) for n?0 where i₁,…, i_r is a permutation of 1,…, n. Here we extend this characterization to the set of normal forms, showing that the only normal forms possessing inverse in the λ-βη-calculus are the “hereditarily finite permutators” (h.f.p.), whose recursive definition is: if n?0, P_j (1?j?n) are h.f.p. and i₁,…,i_n is a permutation of 1,…, n, then the normal form of P = λzλx₁…λx_n(z(P₁x_i1))… (P_nin) is an h.f.p.     

Decomposition of Polynomials with Respect to the Cyclic Group of Orderm

Given a polynomial solution of a differential equation, its m -ary decomposition, i.e. its decomposition as a sum of m polynomials P^{[ j ]}(x)  = ∑_kα_j,kx^{λ_{j, k}}containing only exponentsλ_{j, k} with λ_{j,k  + 1} − λ_j,k = m, is considered. A general algorithm is proposed in order to build holonomic equations for the m -ary parts P^{[ j ]}(x) starting from the initial one, which, in addition, provides a factorized form of them. Moreover, these differential equations are used to compute expansions of the m -ary parts of a given polynomial in terms of classical orthogonal polynomials. As illustration, binary and ternary decomposition of these classical families are worked out in detail.     

Automating Pólya Theory: The Computational Complexity of the Cycle Index Polynomial

In this paper we investigate the computational difficulty of evaluating and approximately evaluating Pólya′s cycle index polynomial. We start by investigating the difficulty of determining a particular coefficient of the cycle index polynomial. In particular, we consider the following problem, in which i is taken to be a fixed positive integer: Given a set of generators for a permutation group G whose degree, n, is a multiple of i, determine the coefficient of x^n/i_i in the cycle index polynomial of G. We show that this problem is #P-hard for every fixed i >1. Next, we consider the evaluation problem. Let y₁, y₂, ... stand for an arbitrary fixed sequence of non-negative real numbers. The cycle index evaluation problem that is associated with this sequence is the following: Given a set of generators for a degree n permutation group G, evaluate the cycle index polynomial of G at the point (y₁, ..., y_n). We show that if there exists an i such that y_i ≠ yⁱ₁ and y_i ≠ 0 then the evaluation problem associated with y₁, y₂, ..., is #P-hard. We observe that the evaluation problem is solvable in polynomial time if y_j = y^j₁ for every positive integer j and that it is solvable in polynomial time if y_j = 0 for every integer j >1. Finally, we consider the approximate evaluation problem. We show that it is NP-hard to approximately solve the evaluation problem if there exists an i such that y_i > yⁱ₁. Furthermore, we show that it is NP-hard to approximately solve the evaluation problem if y₁ = y₂ = ··· = y for some positive non-integer y. We derive some corollaries of our results which deal with the computational difficulty of counting equivalence classes of combinatorial structures.     

Rank and eigenvalues of a supersymmetric tensor, the multivariate homogeneous polynomial and the algebraic hypersurface it defines

A real n-dimensional homogeneous polynomial f(x) of degree m and a real constant c define an algebraic hypersurface S whose points satisfy f(x)=c. The polynomial f can be represented by Ax^m where A is a real mth order n-dimensional supersymmetric tensor. In this paper, we define rank, base index and eigenvalues for the polynomial f, the hypersurface S and the tensor A. The rank is a nonnegative integer r less than or equal to n. When r is less than n, A is singular, f can be converted into a homogeneous polynomial with r variables by an orthogonal transformation, and S is a cylinder hypersurface whose base is r-dimensional. The eigenvalues of f, A and S always exist. The eigenvectors associated with the zero eigenvalue are either recession vectors or degeneracy vectors of positive degree, or their sums. When c⁄=0, the eigenvalues with the same sign as c and their eigenvectors correspond to the characterization points of S, while a degeneracy vector generates an asymptotic ray for the base of S or its conjugate hypersurface. The base index is a nonnegative integer d less than m. If d=k, then there are nonzero degeneracy vectors of degree k−1, but no nonzero degeneracy vectors of degree k. A linear combination of a degeneracy vector of degree k and a degeneracy vector of degree j is a degeneracy vector of degree k+j−m if k+j≥m. Based upon these properties, we classify such algebraic hypersurfaces in the nonsingular case into ten classes.