The Space Complexity of Approximating the Frequency Moments

The frequency moments of a sequence containingm_ielements of typei, 1⩽i⩽n, are the numbersF_k=∑ⁿ_i=1 m^k_i. We consider the space complexity of randomized algorithms that approximate the numbersF_k, when the elements of the sequence are given one by one and cannot be stored. Surprisingly, it turns out that the numbersF₀,F₁, andF₂can be approximated in logarithmic space, whereas the approximation ofF_kfork⩾6 requiresn^Ω(1)space. Applications to data bases are mentioned as well.     

Improving bounds on link failure tolerance of the star graph

Determination of the minimum number of faulty links, f(n,k), that make every n-k-dimensional sub-star graph S_n-k faulty in an n-dimensional star network S_n, has been the subject of several studies. Bounds on f(n,k) have already been derived, and it is known that f(n,1)=n+2. Here, we improve the bounds on f(n,k). Specifically, it is shown that f(n,k)?(k+1)F(n,k), where F(n,k) is the minimum number of faulty nodes that make every S_n-k faulty in S_n. The complexity of f(n,k) is shown to be O(n²k) which is an improvement over the previously known upper bound of O(n³); this result in a special case leads to f(n,2)=O(n^↑2), settling a conjecture introduced in an earlier paper. A systematic method to derive the labels of the faulty links in case of f(n,1) is also introduced.     

Diameter variability of cycles and tori

The diameter of a graph is an important factor for communication as it determines the maximum communication delay between any pair of processors in a network. Graham and Harary [N. Graham, F. Harary, Changing and unchanging the diameter of a hypercube, Discrete Applied Mathematics 37/38 (1992) 265-274] studied how the diameter of hypercubes can be affected by increasing and decreasing edges. They concerned whether the diameter is changed or remains unchanged when the edges are increased or decreased. In this paper, we modify three measures proposed in Graham and Harary (1992) to include the extent of the change of the diameter. Let D^-k(G) is the least number of edges whose addition to G decreases the diameter by (at least) k, D⁺⁰(G) is the maximum number of edges whose deletion from G does not change the diameter, and D^+k(G) is the least number of edges whose deletion from G increases the diameter by (at least) k. In this paper, we find the values of D^-k(C_m), D^-1(T_m,n), D^-2(T_m,n), D⁺¹(T_m,n), and a lower bound for D⁺⁰(T_m,n) where C_m be a cycle with m vertices, T_m,n be a torus of size m by 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.     

Sieve algorithms for perfect power testing

A positive integern is a perfect power if there exist integersx andk, both at least 2, such thatn=x ^k . The usual algorithm to recognize perfect powers computes approximatekth roots forklog ₂ n, and runs in time O(log³ n log log logn).First we improve this worst-case running time toO(log³ n) by using a modified Newton's method to compute approximatekth roots. Parallelizing this gives anNC ² algorithm.Second, we present a sieve algorithm that avoidskth-root computations by seeing if the inputn is a perfectkth power modulo small primes. Ifn is chosen uniformly from a large enough interval, the average running time isO(log² n).Third, we incorporate trial division to give a sieve algorithm with an average running time ofO(log² n/log² logn) and a median running time ofO(logn).The two sieve algorithms use a precomputed table of small primes. We give a heuristic argument and computational evidence that the largest prime needed in this table is (logn)^1+O(1); assuming the Extended Riemann Hypothesis, primes up to (logn)^2+O(1) suffice. The table can be computed in time roughly proportional to the largest prime it contains.We also present computational results indicating that our sieve algorithms perform extremely well in practice.This work forms part of the second author's Ph.D. thesis at the University of Wisconsin-Madison, 1991. This research was sponsored by NSF Grants CCR-8552596 and CCR-8504485.     

Computing largest empty circles with location constraints

LetQ = {q₁, q₂,..., q_n} be a set ofn points on the plane. The largest empty circle (LEG) problem consists in finding the largest circleC with center in the convex hull ofQ such that no pointq _i εQ lies in the interior ofC. Shamos recently outlined anO(n logn) algorithm for solving this problem.⁽⁹⁾ In this paper it is shown that this algorithm does not always work correctly. A different approach is proposed here and shown to also result in anO(n logn) algorithm. The new approach has the advantage that it can also solve more general problems. In particular, it is shown that if the center ofC is constrained to lie in an arbitrary convexn-gon, an0(n logn) algorithm can still be obtained. Finally, an0(n logn +k logn) algorithm is given for solving this problem when the center ofC is constrained to lie in an arbitrary simplen-gonP. wherek denotes the number of intersections occurring between edges ofP and edges of the Voronoi diagram ofQ andk ?O(n ²).     

Boolean-width of graphs

We introduce the graph parameter boolean-width, related to the number of different unions of neighborhoods-Boolean sums of neighborhoods-across a cut of a graph. For many graph problems, this number is the runtime bottleneck when using a divide-and-conquer approach. For an n-vertex graph given with a decomposition tree of boolean-width k, we solve Maximum Weight Independent Set in time O(n²k2^2k) and Minimum Weight Dominating Set in time O(n²+nk2^3k). With an additional n² factor in the runtime, we can also count all independent sets and dominating sets of each cardinality.Boolean-width is bounded on the same classes of graphs as clique-width. boolean-width is similar to rank-width, which is related to the number of GF(2)-sums of neighborhoods instead of the Boolean sums used for boolean-width. We show for any graph that its boolean-width is at most its clique-width and at most quadratic in its rank-width. We exhibit a class of graphs, the Hsu-grids, having the property that a Hsu-grid on Θ(n²) vertices has boolean-width Θ(logn) and rank-width, clique-width, tree-width, and branch-width Θ(n).     

Asymptotic behavior of nonoscillatory solutions of neutral difference equations

The authors consider the m^th-order neutral difference equation D_m(y(n) + p(n)y(n − k) + q(n)f(y(σ(n))) = e(n), where m ≥ 1, {p(n)}, {q(n)}, {e(n)}, and {a₁(n)}, {a₂(n)}, …, {a_m−1(n)} are real sequences, a_i(n) > 0 for i = 1,2,…, m−1, a_m(n) ≡ 1, D₀z(n) = y(n)+p(n)y(n − k), D_iz(n) = a_i(n)ΔD_i−1z(n) for i = 1,2, …, m, k is a positive integer, {σ(n)} → ∞ is a sequence of positive integers, and R → R is continuous with u f(u) > 0 for u ≠ 0. In the case where {q(n)} is allowed to oscillate, they obtain sufficient conditions for all bounded nonoscillatory solutions to converge to zero, and if {q(n)} is a nonnegative sequence, they establish sufficient conditions for all nonoscillatory solutions to converge to zero. Examples illustrating the results are included throughout the paper.     

Modified nonlinearly dispersive mK(m,n,k) equations: I. New compacton solutions and solitary pattern solutions

In this paper exact solutions of the modified nonlinearly dispersive KdV equations (simply called mK(m,n,k) equations), u^m−1u_t+a(uⁿ)_x+b(u^k)_xxx=0, are investigated by using some direct ansatze. As a result, abundant new compacton solutions: solitons with the absence of infinite wings, solitary pattern solutions having infinite slopes or cups, solitary wave solutions and periodic wave solutions are obtained.     

Factorization of disconjugate higher-order Sturm-Liouville difference operators

Using a recently proved equivalence between disconjugacy of the 2n^th-order difference equation

and solvability of the corresponding Riccati matrix difference equation, it is shown that the equation L(y) = 0 is disconjugate on a given interval if and only if the operator L admits the factorization of the form

L(y)_k+n=M^*(c_kM(y)_k)_k+n,

where M and its adjoint M* are certain n^th-order difference operators and c_k is a sequence of positive numbers.     

Almost Exact Matchings

In the exact matching problem we are given a graph G, some of whose edges are colored red, and a positive integer k. The goal is to determine if G has a perfect matching, exactly k edges of which are red. More generally if the matching number of G is m=m(G), the goal is to find a matching with m edges, exactly k edges of which are red, or determine that no such matching exists. This problem is one of the few remaining problems that have efficient randomized algorithms (in fact, this problem is in RNC), but for which no polynomial time deterministic algorithm is known. Our first result shows that, in a sense, this problem is as close to being in P as one can get. We give a polynomial time deterministic algorithm that either correctly decides that no maximum matching has exactly k red edges, or exhibits a matching with m(G)?1 edges having exactly k red edges. Hence, the additive error is one. We also present an efficient algorithm for the exact matching problem in families of graphs for which this problem is known to be tractable. We show how to count the number of exact perfect matchings in K _3,3-minor free graphs (these include all planar graphs as well as many others) in O(n ^3.19) worst case time. Our algorithm can also count the number of perfect matchings in K _3,3-minor free graphs in O(n ^2.19) time.     

Eine stets quadratisch konvergente Modifikation des Steffensen-Verfahrens

It is shown that the following modification of the Steffensen procedurex _n+1=x _n ?k _s (x _n )f(x _n ) (f[x _n ,x _n ?f(x _n )])^?1 (n=0,1,...) withk _s (x)=(1?z _s (x))^?1,z _s (x)=f(x) 2f[x?f(x),x,x+f(x)]×(f[x,x?f(x)])^?2 is quadratically convergent to the root of the equation \(f(x) = (x - \bar x)^p g(x) = 0(p > 0,g(\bar x) \ne 0)\) . Furthermore \(\mathop {\lim }\limits_{n \to \infty } k_s (x_n ) = p\) holds.     

Erzeugende Funktionen bei Spline-Interpolation mit äquidistanten Knoten

Using generating functions we obtain in the case ofn+1 equidistant data points a method for the calculation of the interpolating spline functions(x) of degree 2k+1 with boundary conditionss ^(κ) (x₀)=y ₀ ^(κ) ,s ^(κ) (x _n )=y _n ^(κ) , κ=1(1)k, which only needs the inversion of a matrix of orderk. The applicability of our method in the case of general boundary conditions is also mentioned.     

On fragments of words

We find a precise value of the function F _N(m, n, k), which is the number of binary words of length N and weight m that contain an arbitrary word of length n and weight k as a fragment. As a consequence, we obtain a known result on the number of binary words of length N that contain a fixed word of length n as a fragment.     

PI k mass production and an optimal circuit for the Nečiporuk slice

Letf: {0,1} ⁿ {0,1} ^m be anm-output Boolean function inn variables.f is called ak-slice iff(x) equals the all-zero vector for allx with Hamming weight less thank andf(x) equals the all-one vector for allx with Hamming weight more thank. Wegener showed that PI _k -set circuits (set circuits over prime implicants of lengthk) are at the heart of any optimum Boolean circuit for ak-slicef. We prove that, in PI _k -set circuits, savings are possible for the mass production of anyFX, i.e., any collectionF ofm output-sets given any collectionX ofn input-sets, if their PI _k -set complexity satisfiesSC _m (FX)3n+2m. This PI _k mass production, which can be used in monotone circuits for slice functions, is then exploited in different ways to obtain a monotone circuit of complexity 3n+o(n) for the Neiporuk slice, thus disproving a conjecture by Wegener that this slice has monotone complexity (n ^3/2). Finally, the new circuit for the Neiporuk slice is proven to be asymptotically optimal, not only with respect to monotone complexity, but also with respect to combinational complexity.     

Karnaugh map analysis and synthesis of threshold functions

A unate function can easily be identified on a Karnaugh map from the well-known property that it consists only of essential prime implicants which intersect at a common implicant. The additional property that the plot of a unate function F(x₁ ?x_n ) on a Karnaugh map should possess in order that F may also be 1-realizable (n≤6) has been found. It has been shown that the 1-realizability of a unate function F corresponds to the ‘ compactness ’ of the plot of F. No resort to the inequalities is made, and no pre-processing such as positivizing and ordering of the given function is required.     

On depth in EDTOL languages

Languages of the form L₁={aⁿ:n?1}, L₂={(abⁿ)^m: n,m?1}, L₃={(a(bcⁿ) ^m)^k: n,m,k?1}, etc. differ in what may be called ‘depth’. It turns out that this depth is closely related to the structure of finite state automata associated with EDTOL systems generating these languages. For a given system the corresponding automaton is defined, and the relevant characteristics of its structure are examined.     

Cyclic codes over R = Fp + uFp +?+ uFp with length pn

In this paper, all cyclic codes with length p^sn, (n prime to p) over the ring R = F_p + uF_p +?+ u^k−1F_p are classified. It is first proved that Tor_j(C) is an ideal of , so that the structure of ideals over extension ring S_u^k(m,ω)=GR(u^k,m)[ω]/〈ω^ps-1〉 is determined. Then, an isomorphism between R[X]/〈X^N − 1〉 and a direct sum ⊕_h∈IS_u^k(m_h,ω) can be obtained using discrete Fourier transform. The generator polynomial representation of the corresponding ideals over F_p + uF_p +?+ u^k−1F_p is calculated via the inverse isomorphism. Moreover, torsion codes, MS polynomial and inversion formula are described.     

Parallel Algorithms for Counting and Randomly Generating Integer Partitions

This paper presents parallel algorithms for determining the number of partitions of a given integerN, where the partitions may be subject to restrictions, such as being composed of distinct parts, of a given number of parts, and/or of parts belonging to a specified set. We present a series of adaptive algorithms suitable for varying numbers of processors. The fastest of these algorithms computes the number of partitions ofnwith largest part equal tok, for 1 ≤k≤n≤N, in timeO(log²(N)) usingO(N²/logN) processors. Parallel logarithmic time algorithms that generate partitions uniformly at random, using these quantities, are also presented.