An efficient parallel strategy for the two-fixed-endpoint Hamiltonian path problem on distance-hereditary graphs

In this paper, we solve the two-fixed-endpoint Hamiltonian path problem on distance-hereditary graphs efficiently in parallel. Let T_d(|V|,|E|) and P_d(|V|,|E|) denote the parallel time and processor complexities, respectively, required to construct a decomposition tree of a distance-hereditary graph G=(V,E) on a PRAM model M_d. We show that this problem can be solved in O(T_d(|V|,|E|)+log|V|) time using O(P_d(|V|,|E|)+(|V|+|E|)/log|V|) processors on M_d. Moreover, if G is represented by its decomposition tree form, the problem can be solved optimally in O(log|V|) time using O((|V|+|E|)/log|V|) processors on an EREW PRAM. We also obtain a linear-time algorithm which is faster than the previous known O(|V|³) sequential algorithm.     

Worst-case optimal algorithm for XPath evaluation over XML streams

We consider the XPath evaluation problem: Evaluate an XPath query Q on a streaming XML document D; i.e., determine the set Q(D) of document elements selected by Q. We mainly consider Conjunctive XPath queries that involve only the child and descendant axes. Previously known in-memory algorithms for this problem use O(|D|) space and O(|Q||D|) time. Several previously known algorithms for the streaming version use Ω(dn) space and Ω(dn|D|) time in the worst case; d denotes the depth of D, and n denotes the number of location steps in Q. Their exponential space requirement could well exceed the O(|D|) space used by the in-memory algorithms. We present an efficient algorithm that uses O(d|Q|+nc) space and O((|Q|+dn)|D|) time in the worst case; c denotes the maximum number of elements of D that can be candidates for output, at any one instant. For some worst case Q and D, the memory space used by our algorithm matches our lower bound proved in a different paper; so, our algorithm uses optimal memory space in the worst case.     

Efficient indexing algorithms for one-dimensional discretely-scaled strings

The discretely-scaled string indexing problem asks one to preprocess a given text string T, so that for a queried pattern P, the matched positions in T that P appears with some discrete scale can be reported efficiently. For solving this problem, Wang et al. first show that with an O(|T|log|T|)-time preprocessing on T, all matched positions can be reported in O(|P|+Ud) time, where |T|, |P|, and Ud denote the length of T, the length of P, and the number of matched positions for discretely-scaled P in T, respectively. In this paper, for fixed alphabets we propose the first-known optimal indexing algorithm that takes O(|T|) and O(|P|+Ud) time in its preprocessing and query phases, respectively. For integer and unbounded alphabets, our new algorithm can also be extended to obtain the best-known results.     

A fast algorithm for the alpha-connected two-center decision problem

This paper considers the problem of determining whether a set of points can be covered by two discs with centers p and q and common radius r, such that the ratio d(p,q)/r is bounded below by a specified constant, α. An O(n²log²n) algorithm for solving this problem is also presented.     

On the average depth of asymmetric LC-tries

Andersson and Nilsson have already shown that the average depth Dn of random LC-tries is only Θ(log^∗n) when the keys are produced by a symmetric memoryless process, and that Dn=O(loglogn) when the process is asymmetric. In this paper we refine the second estimate by showing that asymptotically (with n→∞): , where n is the number of keys inserted in a trie, η=−log(1−h/h−∞), h=−plogp−qlogq is the entropy of a binary memoryless source with probabilities p, q=1−p (p≠q), and h−∞=−logmin(p,q).     

Computing Associative Functions Distributively in Spite of Link Failures

Repeated computation of associative functions is central to many asynchronous distributed algorithms reported in the literature. We present efficient distributed algorithms for computing associative functions in spite of undetectable link failures in non-partitioned distributed systems. Two distributed; algorithms are presented for function computation assuming that the distributed system is preprocessed by a one-time preprocessing step that uses O(|E| |V|) messages (where |E| and |V| are the number of links and the number of nodes of the system, respectively). The first algorithm tolerates single link failures using O(|V| log |V|) messages and the second algorithm, which is an extension of the first algorithm, copes with the simultaneous failure of k links using O(k|E| log |V|) messages. Efficient computation of associative functions in the presence of multiple link failures has been an open problem, and our work solves this open problem.     

Cryptanalysis of RSA with two decryption exponents

In this paper, we consider RSA with N=pq, where p,q are of same bit size, i.e., q<p<2q. We study the weaknesses of RSA when multiple encryption and decryption exponents are considered with same RSA modulus N. A decade back, Howgrave-Graham and Seifert (CQRE 1999) studied this problem in detail and presented the bounds on the decryption exponents for which RSA is weak. For the case of two decryption exponents, the bound was N^0.357. We have exploited a different lattice based technique to show that RSA is weak beyond this bound. Our analysis provides improved results and it shows that for two exponents, RSA is weak when the RSA decryption exponents are less than N^0.416. Moreover, we get further improvement in the bound when some of the most significant bits (MSBs) of the decryption exponents are same (but unknown).     

Fraction interpolation walking a Farey tree

We present an algorithm to find a proper fraction in simplest reduced terms between two reduced proper fractions. A proper fraction is a rational number m/n with m<n and n>1. A fraction m/n is simpler than p/q if m?p and n?q, with at least one inequality strict. The algorithm operates by walking a Farey tree in maximum steps down each branch. Through Monte Carlo simulation, we find that the present algorithm finds a simpler interpolation of two fractions than using the Euclidean-Convergent [D.W. Matula, P. Kornerup, Foundations of finite precision rational arithmetic, Computing 2 (Suppl.) (1980) 85-111] walk of a Farey tree and terminating at the first fraction satisfying the bound. Analysis shows that the new algorithms, with very high probability, will find an interpolation that is simpler than at least one of the bounds, and thus take less storage space than at least one of the bounds.     

The complexity of comparability graph recognition and coloring

Using the notion ofG-decomposition introduced in Golumbic [8, 9], we present an implementation of an algorithm which assigns a transitive orientation to a comparability graph inO(δ·|E|) time andO(|E|) space where δ is the maximum degree of a vertex and |E| is the number of edges. A quotient operation reducing the graph in question and preservingG-decomposition and transitive orientability is shown, and efficient solutions to a number ofNP-complete problems which reduce to polynomial time for comparability graphs are discussed.     

A Simpler and More Efficient Algorithm for the Next-to-Shortest Path Problem

Given an undirected graph G=(V,E) with positive edge lengths and two vertices s and t, the next-to-shortest path problem is to find an st-path which length is minimum amongst all st-paths strictly longer than the shortest path length. In this paper we show that the problem can be solved in linear time if the distances from s and t to all other vertices are given. Particularly our new algorithm runs in O(|V|log|V|+|E|) time for general graphs, which improves the previous result of O(|V|²) time and takes only linear time for unweighted graphs, planar graphs, and graphs with positive integer edge lengths.     

An improved algorithm for the red-blue hitting set problem with the consecutive ones property

Let S be a set of elements. We say that a collection C of subsets of S has the consecutive ones property if there exist a linear order on S and a 0-1 matrix M, where Mij=1 if and only if the jth element is in the ith set in C, such that all 1's appear consecutively in each row of M. A set X∈C is hit by a subset S^′⊆S if X∩S^′≠∅. Let Cr (red collection) and Cb (blue collection) be two collections of subsets of S respectively. The red-blue hitting set problem asks for a subset S^′⊆S such that all sets in the blue collection are hit by S^′, while the number of sets in the red collection hit by S^′ has to be minimum. We present a shortest-path based algorithm with time complexity O(|Cb||S|+|Cr||S|+²|S|) for this problem with Cr∪Cb having the consecutive ones property, which improves the previous time bound O(|Cr||Cb|²|S|) by Dom et al. (2008) [8].     

An upper bound for the distance between a zero and a critical point of a solution of a second order linear differential equation

This paper presents an upper bound for the distance between a zero and a critical point of a solution of the second order linear differential equation (p(x)y^′)^′+q(x)y(x)=0, with p(x),q(x)>0. It also compares it with previous results.     

On the complexity of regular resolution and the Davis-Putnam procedure

For infinitely many n > 0 we construct contradictory formulas α_n in conjunctive form with n literals such that every regular proof tree which proves the contradiction must contain 2^cn distinct clauses for some c > 0. This implies a 2^cn lower bound for the number of distinct clauses which are generated by the Davis-Putnam procedure applied to α_n using any order of variable elimination.     

A variant of Wiener’s attack on RSA

Wiener’s attack is a well-known polynomial-time attack on a RSA cryptosystem with small secret decryption exponent d, which works if d < n ^0.25, where n = pq is the modulus of the cryptosystem. Namely, in that case, d is the denominator of some convergent p _m /q _m of the continued fraction expansion of e/n, and therefore d can be computed efficiently from the public key (n, e). There are several extensions of Wiener’s attack that allow the RSA cryptosystem to be broken when d is a few bits longer than n ^0.25. They all have the run-time complexity (at least) O(D ²), where d = Dn ^0.25. Here we propose a new variant of Wiener’s attack, which uses results on Diophantine approximations of the form |α ? p/q| <  c/q ², and “meet-in-the-middle” variant for testing the candidates (of the form rq _m+1 +  sq _m ) for the secret exponent. This decreases the run-time complexity of the attack to O(D log D) (with the space complexity O(D)).     

Q-ary search with one lie and bi-interval queries

The following search game is considered: there are two players, say Paul (or questioner) and Carole (or responder). Carole chooses a number x^*∈Sn={1,2,…,n}, Paul has to find the number x^* by asking q-ary bi-interval queries and Carole is allowed to lie at most once throughout the game. The minimum worst-case number LB(n,q,1) of q-ary bi-interval queries necessary to guess the number x^* is determined exactly for all integers n?1 and q?2. It turns out that LB(n,q,1) coincides with the minimum worst-case number L(n,q,1) of arbitrary q-ary queries.     

The fast Fourier transform for general order

An elementary and transparent representation of the fast Fourier transform is given. Instead of using the usual and highly algebraic approach it is shown how a Fourier transform of the ordern=p·m can be reduced top Fourier transforms of orderm by performing essentiallym Fourier transforms of orderp on the data. The resulting process is discussed in more detail forn=3 ^q andn=5 ^q . The problem of retrieval of the wanted coefficients from the final data is solved by a simple argument. The generalization for an ordern equal to a product of powers of prime numbers is immediate.     

A Deterministic Construction of Normal Bases With Complexity O(n3 + n log n log(log n) log q)

Constructing normal bases of GF(qⁿ) over GF (q) can be done by probabilistic methods as well as deterministic ones. In the following paper we consider only deterministic constructions. As far as we know, the best complexity for probabilistic algorithms is O(n² log⁴n log² (log n) + n log n log (log n) log q ) (see von zur Gathen and Shoup, 1992). For deterministic constructions, some prior ones, e.g. Lueneburg (1986), do not use the factorization of Xⁿ - 1 over GF(q). As analysed by Bach, Driscoll and Shallit (1993), the best complexity (from Lueneburg, 1986) is O(n³ log n log(log n) + n² log n log(log n) log q). For other deterministic constructions, which need such a factorization, the best complexities are O(n^3,376 + n² log n log(log n) log q) (von zur Gathen and Giesbrecht, 1990), or O(n³ log q); see Augot and Camion (1993). Here we propose a new deterministic construction that does not require the factorization of Xⁿ - 1. Its complexity is reduced to O (n³ + n log n log(log n) log q ).     

On the linear complexity of some new q-ary sequences

Some new q-ary sequences with period q^3ek-1 (q=p^m, p an odd prime, m, e, k integers) are first constructed and then, inspired by Antweiler’s method, their linear complexity is examined. The exact value of linear complexity k(6e)^w is determined when . Furthermore, an upper bound of the linear complexity is given for the other values of r. Our results show that this sequence has larger linear span than GMW sequence with the same parameters. Finally, the results of a Maple program are included to illustrate the validity of the results.     

Complexity aspects of generalized Helly hypergraphs

In [V.I. Voloshin, On the upper chromatic number of a hypergraph, Australas. J. Combin. 11 (1995) 25-45], Voloshin proposed the following generalization of the Helly property. Let p?1, q?0 and s?0. A hypergraph H is (p,q)-intersecting when every partial hypergraph H^′⊆H formed by p or less hyperedges has intersection of cardinality at least q. A hypergraph H is (p,q,s)-Helly when every partial (p,q)-intersecting hypergraph H^′⊆H has intersection of cardinality at least s. In this work, we study the complexity of determining whether H is (p,q,s)-Helly.