Search

In this paper, by constructing a more entangled quantum system, we shorten the adiabatic quantum search algorithm to constant time. On the other hand, we show that the speed-up of adiabatic quantum algorithms by selecting particular adiabatic evolution paths or injecting energy into the quantum system can be explained as a form of entanglement enlargement. These findings suggest that entanglement plays a fundamental role for the efficiency of algorithm performance. [ABSTRACT FROM AUTHOR]

This paper studies the complexity of determining if a finite algebra generates a variety that satisfies various Maltsev conditions, such as congruence distributivity or modularity. For idempotent algebras we show that there are polynomial time algorithms to test for these conditions but that in general these problems are EXPTIME complete. In addition, we provide sharp bounds in terms of the size of two-generated free algebras on the number of terms needed to witness various Maltsev conditions, such as congruence distributivity. [ABSTRACT FROM AUTHOR]

This paper studies the two-dimensional range search problem, and constructs a simple and efficient algorithm based on the Voronoi diagram. In this problem, a set of points and a query range are given, and we want to enumerate all the points which are inside the query range as quickly as possible. In most of the previous researches on this problem, the shape of the query range is restricted to particular ones such as circles, rectangles and triangles, and the improvement on the worst-case performance has been pursued. On the other hand, the algorithm proposed in this paper is designed for a general shape of the query range in the two-dimensional space, and is intended to accomplish a good average-case performance. This performance is actually observed by numerical experiments. In these experiments, we compare the execution time of the proposed algorithm with those of other representative algorithms such as those based on the bucketing technique and the k-d tree. We can observe that our algorithm shows the better performance in almost all the cases. [ABSTRACT FROM AUTHOR]

This paper describes an efficient and adaptive method of threshold estimation for removing impulse noise from images, based on Double Density Wavelet Transform (DDWT). The performance of image de-noising algorithms using wavelet transforms can be improved significantly by fixing an optimum threshold value, based on the analysis of the statistical parameters of subband coefficients. In this proposed method, the choice of the threshold estimation is carried out by analyzing the statistical parameters of the wavelet subband coefficients like standard deviation, arithmetic mean and geometrical mean. Here the noisy image is first decomposed into many levels to obtain different frequency bands using DDWT. Then soft thresholding method is used to remove the noisy coefficients, by fixing the optimum threshold value by the proposed method. Experimental results on several test images by using the proposed method show that, the proposed method yields significantly superior image quality and better Peak Signal-to-Noise Ratio (PSNR). Some comparisons with the best available results will be given in order to illustrate the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

An algorithm is proposed in this paper that finds exact exclusive-or sum-of-products of an arbitrary function, provided the number of product terms is less than eight. If the number of product terms in the minimal expression is more than seven, then the algorithm detects it and heuristically returns near-optimal expressions. The algorithm is time and space efficient even for functions with many input variables. [ABSTRACT FROM AUTHOR]

In this paper, we consider a set of mobile nodes, each of which moves with constant velocity. We present algorithms to determine which of these mobile nodes can be captured the soonest by a set of one or more pursuers. We use a time parameterized R-tree (TPR-tree) to index these moving points. We then develop algorithms that operate on the TPR-tree to answer three query variations: (1) a single pursuer that is faster than all of the mobile nodes, (2) a single pursuer that is slower than some of the mobile nodes and (3) multiple pursuers. Experimental results show that our algorithms are simpler and faster than other approaches to solve the problem. [ABSTRACT FROM AUTHOR]

It is shown that given any link-manifold, there is an algorithm to decide if the manifold contains an embedded, essential planar surface; if it does, the algorithm will construct one. Two similar results are obtained with added boundary conditions. Namely, given a link-manifold M, a component B of ∂M, and a slope γ on B, there is an algorithm to decide if there is an embedded punctured-disk in M with boundary γ and punctures in ∂M\B; and given a link-manifold M, a component B of ∂M, and a meridian slope μ on B, there is an algorithm to decide if there is an embedded punctured-disk with boundary a longitude on B and punctures in ∂M\B. In both cases, if there is one, the algorithm will construct one. The proofs introduce a number of new methods and differ from the classical proofs, using normal surfaces, as solutions may not be found among the fundamental solutions. [ABSTRACT FROM AUTHOR]

We give an algorithm for deciding whether an embedding of a finite partial order ${\mathcal P}$ into the enumeration degrees of the ${\Sigma_2^0}$-sets can always be extended to an embedding of a finite partial order ${\mathcal Q} \supset {\mathcal P}$. [ABSTRACT FROM AUTHOR]