O(log n) bimodality analysis

The bimodality of a population P can be measured by dividing its range into two intervals so as to maximize the Fisher distance between the resulting two subpopulations P₁ and P₂. If P is a mixture of two (approximately) Gaussian subpopulations, then P₁ and P₂ are good approximations to the original Gaussians, if their Fisher distance is great enough. Moreover, good approximations to P₁ and P₂ can be obtained by dividing P into small parts; finding the maximum-distance (MD) subdivision of each part; combining small groups of these subdivisions into (approximate) MD subdivisions of larger parts; and so on. This divide-and-conquer approach yields an approximate MD subdivision of P in O(log n) computational steps using O(n) processors, where n is the size of P.     

Computing the Quartet Distance between Evolutionary Trees in Time O( n log n)

Evolutionary trees describing the relationship for a set of species are central in evolutionary biology, and quantifying differences between evolutionary trees is therefore an important task. The quartet distance is a distance measure between trees previously proposed by Estabrook, McMorris, and Meacham. The quartet distance between two unrooted evolutionary trees is the number of quartet topology differences between the two trees, where a quartet topology is the topological subtree induced by four species. In this paper we present an algorithm for computing the quartet distance between two unrooted evolutionary trees of n species, where all internal nodes have degree three, in time O(n log n. The previous best algorithm for the problem uses time O(n ²).     

Computing the Quartet Distance between Evolutionary Trees in Time O ( n log n )

Evolutionary trees describing the relationship for a set of species are central in evolutionary biology, and quantifying differences between evolutionary trees is therefore an important task. The quartet distance is a distance measure between trees previously proposed by Estabrook, McMorris, and Meacham. The quartet distance between two unrooted evolutionary trees is the number of quartet topology differences between the two trees, where a quartet topology is the topological subtree induced by four species. In this paper we present an algorithm for computing the quartet distance between two unrooted evolutionary trees of n species, where all internal nodes have degree three, in time O(n log n. The previous best algorithm for the problem uses time O(n ²).     

Build shape-shifting tries for fast IP lookup in O(n) time

Most data structures for packet forwarding are optimized for IPv4, and less capable of handling IPv6 routing tables. Shape-Shifting Trie (SST) is specifically designed to be scalable to IPv6. To reduce the worst-case lookup time that is proportional to the height of SST, it is desirable to construct a minimum-height SST. Breadth-First Pruning (BFP) algorithm takes O(n²) time to construct a minimum-height SST, where n is the number of nodes in the binary trie corresponding to the routing table. In this paper, we propose a Post-Order Minimum-Height Pruning (POMHP) algorithm that takes only O(n) time to construct a minimum-height SST. We further propose nodes merging algorithm to cut down SST size without affecting SST height.     

A binary algorithm for solving n by n systems of integer equations

We discuss a “binary” algorithm for solving systems of linear equations with integer coefficients. So-called “binary” algorithms differ from ordinary ones in that there is no roundoff error, but only overflow, and the underlying analysis is p-adic analysis rather than conventional real analysis. The advantages of this algorithm are especially apparent when extremely large numbers are involved and no roundoff error can be tolerated.

VLSI implementation of this and other “binary” algorithms is very appealing because of the extreme regularity of the circuits involved.     

Bridging across the log(n) Space Frontier

This paper establishes the importance of even the lowest possible level of space bounded computations. We show that DLOG does not coincide with NLOG if and only if there exists a tally set in NSPACE(log log n)\DSPACE(log log n). This result stands in perfect analogy to the related results concerning linear space or exponential time. Moreover, the above problem is equivalent to the existence of a functions(n), with arbitrarily slow or rapid growth rate, that is nondeterministically fully space constructible but cannot be constructed deterministically. We also present a “hardest” fully space constructibles(n)∈O(log log n), a functional counterpart of log-space complete languages. These nonrelativized results are obtained by the use of oracle machines consuming much larger amount of space, in range betweennand 2^d·n.     

An O(log n) pyramid hough transform

This paper describes a divide-and-conquer Hough transform technique for detecting a given number of straight edges or lines in an image. This technique is designed for implementation on a pyramid of processors, and requires only O(log n) computational steps for an image of size n × n.     

An O ( n 1.5 ) Deterministic Gossiping Algorithm for Radio Networks

   Abstract. We consider the problem of distributed gossiping in radio networks of unknown topology. For radio networks of size n and diameter D , we present an adaptive deterministic gossiping algorithm of time O (

On the uniform finite generation of SO(n, )

A Lie group G, generated by two one-parameter subgroups is said to be uniformly finitely generated by them if there exists a positive integer N such that every element of G can be expressed as a product of at most N elements chosen alternately from the two one-parameter subgroups. In this paper we construct pairs of generators of so(n) whose one-parameter subgroups uniformly finitely generate SO(n) and as a consequence, we put an upper bound on the number of switches required to join any two points on a manifold M trajectories of two particular vector fields on M.     

Embedding k(n−k) edge-disjoint spanning trees in arrangement graphs

The arrangement graphs are a class of generalized star graphs. In this paper we construct a graph that consists of the maximum number of directed edge-disjoint spanning trees in an arrangement graph. The paths that connect the common root node to any given node through different spanning trees are node-disjoint, and the lengths of these paths differ from the shortest possible lengths by a small additive constant. This graph can be used to derive fault-tolerant algorithms for broadcasting and scattering problems without prior knowledge of the faulty elements of the network.     

Constant-Time Tree Algorithms on Reconfigurable Meshes on Size n × n

Recently, an elegant and powerful architecture called the reconfigurable mesh has been proposed in the literature. In essence, a reconfigurable mesh consists of a mesh-connected architecture enhanced by the addition of a dynamic bus system whose configuration changes in response to computational and communication needs. In this paper we show that the reconfigurable mesh architecture can be exploited to yield very simple constant-time algorithms to solve a number of important computational problems involving trees. Specifically, we address the problem of generating the computation tree form of an arithmetic expression, the problem of reconstructing a binary tree from its preorder and inorder traversals, and the problem of reconstructing an ordered forest from its preorder and postorder traversals. We show that with an input of size n, all these problems find constant-time solutions on a reconfigurable mesh of size n × n.     

Computing steady state probabilities in λ(n)/G/1/K queue

In this paper a recursive method is developed to obtain the steady state probability distribution of the number in system at arbitrary and departure time epochs of a single server state-dependent arrival rate queue λ(n)/G/1/K in which the arrival process is Markovian with arrival rates λ(n) which depend on the number of customers n in the system and general service time distribution. It is assumed that there exists an integer K such that λ(n) > 0 for all 0 n < K and λ(n) = 0 for all n K. Numerical results have been presented for many queueing models by suitably defining the function λ(n). These include machine interference model, queues with balking, queues with finite waiting space and machine interference model with finite waiting space. These models have wide application in computer/communication networks.     

A Two-Step Regularization Framework for Non-Local Means

As an effective patch-based denoising method, non-local means （NLM） method achieves favorable denoising performance over its local counterparts and has drawn wide attention in image processing community. The in, plementation of NLM can formally be decomposed into two sequential steps, i.e., computing the weights and using the weights to compute the weighted means. In the first step, the weights can be obtained by solving a regularized optimization. And in the second step, the means can be obtained by solving a weighted least squares problem. Motivated by such observations, we establish a two-step regularization framework for NLM in this paper. Meanwhile, using the fl-amework, we reinterpret several non-local filters in the unified view. Further, taking the framework as a design platform, we develop a novel non-local median filter for removing salt-pepper noise with encouraging experimental results.     

A new way of counting n

In this paper, we shall give a combinatorial proof of the following equation:

,

where m and n are positive integers, m ≤ n, and k₁, k₂, …, k_n-1 are nonnegative integers.     

Exact 3-satisfiability is decidable in time O(20.16254n)

Let F = C ₁ C _m be a Boolean formula in conjunctive normal form over a set V of n propositional variables, s.t. each clause C _i contains at most three literals l over V. Solving the problem exact 3-satisfiability (X3SAT) for F means to decide whether there is a truth assignment setting exactly one literal in each clause of F to true (1). As is well known X3SAT is NP-complete [6]. By exploiting a perfect matching reduction we prove that X3SAT is deterministically decidable in time O(2^0.18674n ). Thereby we improve a result in [2,3] stating X3SAT O(2^0.2072n ) and a bound of O(2^0.200002n ) for the corresponding enumeration problem #X3SAT stated in a preprint [1]. After that by a more involved deterministic case analysis we are able to show that X3SAT O(2^0.16254n ).An extended abstract of this paper was presented at the Fifth International Symposium on the Theory and Applications of Satisfiability Testing (SAT 2002).     

Security of Wang et al.''s group-oriented (t,n) threshold signature schemes with traceable signers

This paper describes a new forgery attack on the group-oriented (t,n) threshold signature schemes proposed by Wang et al. Our attack is more fundamental than Tseng–Jan's attack in the sense that it cannot be recognized or blocked at the designated clerk level of the signature schemes.     

Contrast-optimal k out of n secret sharing schemes in visual cryptography

Visual cryptography and (k,n)-visual secret sharing schemes were introduced by Naor and Shamir (Advances in Cryptology — Eurocrypt 94, Springer, Berlin, 1995, pp. 1–12). A sender wishing to transmit a secret message distributes n transparencies amongst n recipients, where the transparencies contain seemingly random pictures. A (k,n)-scheme achieves the following situation: If any k recipients stack their transparencies together, then a secret message is revealed visually. On the other hand, if only k−1 recipients stack their transparencies, or analyze them by any other means, they are not able to obtain any information about the secret message. The important parameters of a scheme are its contrast, i.e., the clarity with which the message becomes visible, and the number of subpixels needed to encode one pixel of the original picture. Naor and Shamir constructed (k,k)-schemes with contrast 2^−(k−1). By an intricate result from Linial (Combinatorica 10 (1990) 349–365), they were also able to prove the optimality of these schemes. They also proved that for all fixed kn, there are (k,n)-schemes with contrast . For k=2,3,4 the contrast is approximately and . In this paper, we show that by solving a simple linear program, one is able to compute exactly the best contrast achievable in any (k,n)-scheme. The solution of the linear program also provides a representation of a corresponding scheme. For small k as well as for k=n, we are able to analytically solve the linear program. For k=2,3,4, we obtain that the optimal contrast is at least and . For k=n, we obtain a very simple proof of the optimality of Naor's and Shamir's (k,k)-schemes. In the case k=2, we are able to use a different approach via coding theory which allows us to prove an optimal tradeoff between the contrast and the number of subpixels.     

Area-time optimal division for T = Ω((log n))

Area-time optimal VLSI division circuits are described for all computation times in the range for arbitrary > 0.     

Efficient implementation of Johnson''s rule for the n/2/F/Fmax scheduling problem

Several efficient algorithms of O(n log n) computational complexity, for the Johnson's rule to schedule a set of simultaneously available jobs on two machines in a flowship to minimize the maximum job flowtime have appeared in the literature. A modified version of one of these algorithms is presented which not only simplifies the programming effort for implementation but is also able to generate all possible optimal sequences obtainable from Johnson's rule.