Algorithms for Exponentiation in Finite Fields

Gauss periods yield (self-dual) normal bases in finite fields, and these normal bases can be used to implement arithmetic efficiently. It is shown that for a small prime power q and infinitely many integersn , multiplication in a normal basis of Fqn over Fq can be computed with O(n logn loglog n), division with O(n log²n loglog n) operations in Fq, and exponentiation of an arbitrary element in Fqn withO (n²loglog n) operations in Fq. We also prove that using a polynomial basis exponentiation in F 2 n can be done with the same number of operations in F 2 for all n. The previous best estimates were O(n²) for multiplication in a normal basis, andO (n²log n loglog n) for exponentiation in a polynomial basis.     

Fast modular exponentiation of large numbers with large exponents

In many problems, modular exponentiation |x^b|_m is a basic computation, often responsible for the overall time performance, as in some cryptosystems, since its implementation requires a large number of multiplications.It is known that |x^b|_m=|x^|b|_(m)|_m for any x in [1,m−1] if m is prime; in this case the number of multiplications depends on (m) instead of depending on b. It was also stated that previous relation holds in the case m=pq, with p and q prime; this case occurs in the RSA method.In this paper it is proved that such a relation holds in general for any x in [1,m−1] when m is a product of any number n of distinct primes and that it does not hold in the other cases for the whole range [1,m−1].Moreover, a general method is given to compute |x^b|_m without any hypothesis on m, for any x in [1,m−1], with a number of modular multiplications not exceeding those required when m is a product of primes.Next, it is shown that representing x in a residue number system (RNS) with proper moduli m_i allows to compute |x^b|_m by n modular exponentiations |x_i^b|_mi in parallel and, in turn, to replace b by |b|_(mi) in the worst case, thus executing a very low number of multiplications, namely log₂m_i for each residue digit.A general architecture is also proposed and evaluated, as a possible implementation of the proposed method for the modular exponentiation.     

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.     

Solving shortest paths efficiently on nearly acyclic directed graphs

Shortest path problems can be solved very efficiently when a directed graph is nearly acyclic. Earlier results defined a graph decomposition, now called the 1-dominator set, which consists of a unique collection of acyclic structures with each single acyclic structure dominated by a single associated trigger vertex. In this framework, a specialised shortest path algorithm only spends delete-min operations on trigger vertices, thereby making the computation of shortest paths through non-trigger vertices easier. A previously presented algorithm computed the 1-dominator set in O(mn) worst-case time, which allowed it to be integrated as part of an O(mn+nrlogr) time all-pairs algorithm. Here m and n respectively denote the number of edges and vertices in the graph, while r denotes the number of trigger vertices. A new algorithm presented in this paper computes the 1-dominator set in just O(m) time. This can be integrated as part of the O(m+rlogr) time spent solving single-source, improving on the value of r obtained by the earlier tree-decomposition single-source algorithm. In addition, a new bidirectional form of 1-dominator set is presented, which further improves the value of r by defining acyclic structures in both directions over edges in the graph. The bidirectional 1-dominator set can similarly be computed in O(m) time and included as part of the O(m+rlogr) time spent computing single-source. This paper also presents a new all-pairs algorithm under the more general framework where r is defined as the size of any predetermined feedback vertex set of the graph, improving the previous all-pairs time complexity from O(mn+nr²) to O(mn+r³).     

New Plain-Exponential Time Classes for Graph Homomorphism

A homomorphism from a graph G to a graph H (in this paper, both simple, undirected graphs) is a mapping f:V(G)→V(H) such that if uv∈E(G) then f(u)f(v)∈E(H). The problem Hom (G,H) of deciding whether there is a homomorphism is NP-complete, and in fact the fastest known algorithm for the general case has a running time of O ^*(n(H) ^cn(G)) (the notation O ^*(⋅) signifies that polynomial factors have been ignored) for a constant 0<c<1. In this paper, we consider restrictions on the graphs G and H such that the problem can be solved in plain-exponential time, i.e. in time O ^*(c ^n(G)+n(H)) for some constant c.     

Stochastic adaptive pole-zero assignment with convergence analysis

The adaptive control u_n is designed for the stochastic system A(z)y_n+1 = B(z)u_n+C(z)w_n+1 with unknown constant matrix coefficients in the polynomials A(z), B(z) and C(z) in the shift-back operator with the purposes that (1) the unknown matrices are strongly consistently estimated and (2) the poles and zeros are replaced in such a way that the system itself is transferred to A⁰(z)y_n+1 = B⁰(z)u_n⁰+_n+1 with given A⁰(z), B⁰(z) and u_n⁰ so that the pole-zero assignment error {_n+1} is minimized. The problem of adaptive pole-zero assignment combined with tracking is also considered in this paper. Conditions used are imposed only on A(z), B(z) and C(z).     

Efficient Algorithms for Computing a Complete Visibility Region in Three-Dimensional Space

Given a set P of polygons in three-dimensional space, two points p and q are said to be visible from each other with respect to P if the line segment joining them does not intersect any polygon in P . A point p is said to be completely visible from an area source S if p is visible from every point in S . The completely visible region CV(S, P) from S with respect to P is defined as the set of all points in three-dimensional space that are completely visible from S . We present two algorithms for computing CV(S, P) for P with a total of n vertices and a convex polygonal source S with m vertices. Our first result is a divide-and-conquer algorithm which runs in O(m ² n ² α(mn)) time and space, where α(mn) is the inverse of Ackermann's function. We next give an incremental algorithm for computing CV(S,P) in O(m ² n+mn ² α(n)) time and O(mn+n ² ) space. We also prove that CV(S,P) consists of Θ(mn+n ² ) surface elements such as vertices, edges, and faces. Received November 16, 1995; revised November 11, 1996.     

Space Efficient Dynamic Orthogonal Range Reporting

In this paper we present new space efficient dynamic data structures for orthogonal range reporting. The described data structures support planar range reporting queries in time O(log n+klog log (4n/(k+1))) and space O(nlog log n), or in time O(log n+k) and space O(nlog  ^ε n) for any ε>0. Both data structures can be constructed in O(nlog n) time and support insert and delete operations in amortized time O(log ² n) and O(log nlog log n) respectively. These results match the corresponding upper space bounds of Chazelle (SIAM J. Comput. 17, 427–462, 1988) for the static case. We also present a dynamic data structure for d-dimensional range reporting with search time O(log  ^d−1 n+k), update time O(log  ^d n), and space O(nlog  ^d−2+ε n) for any ε>0. The model of computation used in our paper is a unit cost RAM with word size log n. A preliminary version of this paper appeared in the Proceedings of the 21st Annual ACM Symposium on Computational Geometry 2005. Work partially supported by IST grant 14036 (RAND-APX).     

Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology

This paper discusses how to count and generate strings that are ``distinct' in two senses: p -distinct and b -distinct. Two strings x on alphabet A and x' on alphabet A' are said to be p -distinct iff they represent distinct ``patterns'; that is, iff there exists no one—one mapping from A to A' that transforms x into x' . Thus aab and baa are p -distinct while aab and ddc are p -equivalent. On the other hand, x and x' are said to be b -distinct iff they give rise to distinct border (failure function) arrays: thus aab with border array 010 is b -distinct from aba with border array 001 . The number of p -distinct (resp. b -distinct) strings of length n formed using exactly k different letters is the [k,n] entry in an infinite p' (resp. b' ) array. Column sums p[n] and b[n] in these arrays give the number of distinct strings of length n . We present algorithms to compute, in constant time per string, all p -distinct (resp. b -distinct) strings of length n formed using exactly k letters, and we also show how to compute all elements p'[k,n] and b'[k,n] . These ideas and results have application to the efficient generation of appropriate test data sets for many string algorithms. Received December 21, 1995; revised April 28, 1997.     

On Minimum-Area Hulls

We study some minimum-area hull problems that generalize the notion of convex hull to star-shaped and monotone hulls. Specifically, we consider the minimum-area star-shaped hull problem: Given an n -vertex simple polygon P , find a minimum-area, star-shaped polygon P ^* containing P . This problem arises in lattice packings of translates of multiple, nonidentical shapes in material layout problems (e.g., in clothing manufacture), and has been recently posed by Daniels and Milenkovic. We consider two versions of the problem: the restricted version, in which the vertices of P ^* are constrained to be vertices of P , and the unrestricted version, in which the vertices of P ^* can be anywhere in the plane. We prove that the restricted problem falls in the class of ``3sum-hard' (sometimes called ``n ² -hard') problems, which are suspected to admit no solutions in o(n ² ) time. Further, we give an O(n ² ) time algorithm, improving the previous bound of O(n ⁵ ) . We also show that the unrestricted problem can be solved in O(n ² p(n)) time, where p(n) is the time needed to find the roots of two equations in two unknowns, each a polynomial of degree O(n) . We also consider the case in which P ^* is required to be monotone, with respect to an unspecified direction; we refer to this as the minimum-area monotone hull problem. We give a matching lower and upper bound of Θ(n log n) time for computing P ^* in the restricted version, and an upper bound of O(n q(n)) time in the unrestricted version, where q(n) is the time needed to find the roots of two polynomial equations in two unknowns with degrees 2 and O(n) . Received November 1996; revised March 1997.     

Improved Algorithms for Constructing Fault-Tolerant Spanners

Abstract. Let S be a set of n points in a metric space, and let k be a positive integer. Algorithms are given that construct k -fault-tolerant spanners for S . If in such a spanner at most k vertices and/ or edges are removed, then each pair of points in the remaining graph is still connected by a ``short' path. First, an algorithm is given that transforms an arbitrary spanner into a k -fault-tolerant spanner. For the Euclidean metric in R ^d , this leads to an O(n log n + c ^k n) -time algorithm that constructs a k -fault-tolerant spanner of degree O(c ^k ) , whose total edge length is O(c ^k ) times the weight of a minimum spanning tree of S , for some constant c . For constant values of k , this result is optimal. In the second part of the paper, algorithms are presented for the Euclidean metric in R ^d . These algorithms construct (i) in O(n log n + k ² n) time, a k -fault-tolerant spanner with O(k ² n) edges, and (ii) in O(k n log n) time, such a spanner with O(k n log n) edges.     

Fitting a Step Function to a Point Set

We consider the problem of fitting a step function to a set of points. More precisely, given an integer k and a set P of n points in the plane, our goal is to find a step function f with k steps that minimizes the maximum vertical distance between f and all the points in P. We first give an optimal Θ(nlog n) algorithm for the general case. In the special case where the points in P are given in sorted order according to their x-coordinates, we give an optimal Θ(n) time algorithm. Then, we show how to solve the weighted version of this problem in time O(nlog ⁴ n). Finally, we give an O(nh ²log n) algorithm for the case where h outliers are allowed. The running time of all our algorithms is independent of k.     

Direct dominance of points

Several transitive relations of geometrical objects (like inclusion of intervals on a line or polygons in the plain), which are important in VLSI design applications, can be translated into the dominance relation a dominates b iff (a ≠ b and a _j ≧ b _j for j = 1,…d) of points a = (a ₁,...,a _d ),b = (b ₁,…b _d ) in R ^d by representing the objects as points in a suitable way. If only the transitive reduction (see [7]) of the given relation is required and not all the implications by transitivity, one can restrict oneself to the direct dominances in the corresponding point set N; here a dominates b directly means that a dominates b and there is no—with respect to dominance—intermediate c in N (see [5]). To estimate the advantage of this restriction, information about the numbers of dominant and directly dominant pairs in a set of n points is required, both numbers essentially depending upon how the points are distributed in R ^d . In this paper we assume the n points in question to be identically and independently distributed; then we can expect q·n·(n–1) dominance pairs. For a certain class of distributions including the uniform distribution we prove the theorem, that the expected number of direct dominance pairs is asymptotically equal to 1/(d?1)! · n1n ^{d ? 1}(n). Hence algorithms which compute only the direct dominances instead of all dominances are worth to be considered.     

An efficient alignment algorithm for masked sequences

We consider the alignment problem where sequences may have masked regions. The bases in masked regions are either unspecified or unknown, and they will be denoted by N. We present an efficient algorithm that finds an optimal local alignment by skipping such masked regions of sequences. Our algorithm works for both the affine gap penalty model and the linear gap penalty model. The time complexity of our algorithm is O((n−T)(m−S)+vm+wn) time, where n and m are the lengths of given sequences A and B, T and S are the numbers of base N in A and B, and v and w are the numbers of masked regions in A and B, respectively.     

On partitions of functions on finite sets

Let D and R be finite sets with cardinality n and m respectivelyR ^D be the set of all functions from D into R, and G and H be permutation groups acting on D and R respectively. Two functions f and g in R ^D are said to be related if there exists a σ in G and a τ in H with f(σd) = τg(d) for every d in D. Since the relation is an equivalence relation, R ^D is partitioned into disjoint classes. Roughly, by using the cycle indices of G and H, de Bruijn's theorem determines the number of equivalence classes, and Pólya's theorem, with H being the identity group, gives the function counting series, Pólya-de Bruijn's theorem has many applications (for instance, see Pólya and Read [6]). The theorem and its applications, basically, centered around the partitions of functions. Here, we present an algorithm to determine which functions in R ^D belong to the same equivalent class. Our algorithm does not use the cycle indices of G and H (to compute the cycle index of a given group, in general, is difficult), but it uses the generators of G and H, and the m-nary numbers to code the functions in R ^D . Our algorithm also gives the function counting series and the number of equivalence classes. An important application is that for each positive integer n, we use our algorithm and the symmetric group S _n to determine all isomorphic and nonisomorphic graphs and directed graphs with n vertices.     

Independence and k-domination in graphs

A subset S of vertices of a graph G is k-dominating if every vertex not in S has at least k neighbours in S. The k-domination number γ _k (G) is the minimum cardinality of a k-dominating set of G, and α(G) denotes the cardinality of a maximum independent set of G. Brook's well-known bound for the chromatic number χ and the inequality α(G)≥n(G)/χ(G) for a graph G imply that α(G)≥n(G)/Δ(G) when G is non-regular and α(G)≥n(G)/(Δ(G)+1) otherwise. In this paper, we present a new proof of this property and derive some bounds on γ _k (G). In particular, we show that, if G is connected with δ(G)≥k then γ _k (G)≤(Δ(G)?1)α(G) with the exception of G being a cycle of odd length or the complete graph of order k+1. Finally, we characterize the connected non-regular graphs G satisfying equality in these bounds and present a conjecture for the regular case.     

Coincidental extension of scattered context languages

For a symbol, #, and a string, x = a ₁ a ₂ ...a _{n - 1} a _n , any string of the form # ⁱ a ₁ # ⁱ a ₂ # ⁱ...# ⁱ a _{n - 1} # ⁱ a _n # ⁱ, where 0, is a coincidental #-extension of x. A language, K, is a coincidental #-extension of L if every string of K represents a coincidental extension of a string in L and the deletion of all #s in K results in L. This paper proves that for every recursively enumerable language, E, there exists a propagating scattered context language that represents a coincidental extension of E. Received: 31 October 2001 / 31 January 2003     

A Decision Procedure for Linear “Big O” Equations

Let F be the set of functions from an infinite set, S, to an ordered ring, R. For f, g, and h in F, the assertion f = g + O(h) means that for some constant C, |f(x) − g(x)| ≤C |h(x)| for every x in S. Let L be the first-order language with variables ranging over such functions, symbols for 0, +, −, min , max , and absolute value, and a ternary relation f = g + O(h). We show that the set of quantifier-free formulas in this language that are valid in the intended class of interpretations is decidable and does not depend on the underlying set, S, or the ordered ring, R. If R is a subfield of the real numbers, we can add a constant 1 function, as well as multiplication by constants from any computable subfield. We obtain further decidability results for certain situations in which one adds symbols denoting the elements of a fixed sequence of functions of strictly increasing rates of growth.     

An equivalence between rational H2 and Hankel-norm approximations

Let H(z) be a given function in H₂ A classical problem in engineering analysis is to find a rational function G (z) ε H₂ degree M say, which is closest to H(z) in 2-norm. This problem is typically approached using the cost function |H(z) − G(z)|₂, in which G(z) is allowed to vary over the set of Mth-order rational functions in H₂ and for which stationary points are sought. We show that each stationary point of degree M of this functional coincides with a weighted Hankel-norm approximant to H(z). The weighting function derives from the outer factor of the error function H(z) − G(z) stationary point of the rational H₂ approximation problem.