Coefficient Fields of Solutions in Kovacic's Algorithm

In this paper we prove the following theorem: if the Riccati equation w^′ + w² = R(x), R ϵ Q(x), has algebraic solutions, then there exists a minimum polynomial defining such a solution whose coefficients lie at most in a cubic extension of the field Q. In Zharkov (1992), the same result was erroneously stated for, at most, quadratic extensions of Q. However, M. Singer discovered that in some cases the cubic extensions are necessary. Here we give a corrected and more detailed proof of the theorem.     

Absolute convergence of rational series is semi-decidable

This paper deals with absolute convergence of real-valued rational series, i.e. mappings r:Σ^∗→R computed by weighted automata. An algorithm is provided, that takes a weighted automaton A as input and halts if and only if the corresponding series r_A is absolutely convergent: hence, absolute convergence of rational series is semi-decidable. A spectral radius-like parameter ρ_|r| is introduced, which satisfies the following property: a rational series r is absolutely convergent iff ρ_|r|<1. We show that if r is rational, then ρ_|r| can be approximated by convergent upper estimates. Then, it is shown that the sum ∑_w∈Σ^∗|r(w)| can be estimated to any accuracy rate. This result can be extended to any sum of the form ∑_w∈Σ^∗|r(w)|^p, for any integer p.     

A Random Base Change Algorithm for Permutation Groups

A new random base change algorithm is presented for a permutation group G acting on n points whose worst case asymptotic running time is better for groups with a small to moderate size base than any known deterministic algorithm. To achieve this time bound, the algorithm requires a random generator Rand(G) producing a random element of G with the uniform distribution and so that the time for each call to Rand (G) is bounded by some function f(n, G). The random base change algorithm has probability 1 - 1/|G| of completing in time O(f(n, G) log |G|) and outputting a data structure for representing the point stabilizer sequence relative to the new ordering. The algorithm requires O(n log |G|) space and the data structure produced can be used to test group membership in time O(n log |G|). Since the output of this algorithm is a data structure allowing generation of random group elements in time O(n log |G|), repeated application of the random base change algorithms for different orderings of the permutation domain of G will always run in time O (n log² |G|). An earlier version of this work appeared in Cooperman and Finkelstein (1992b).     

Periods in Extensions of Words

Let π(w) denote the minimum period of the word w,let w be a primitive word with period π(w) < |w|, and let z be a prefix of w. It is shown that if π(wz) = π(w), then |z| < π(w) − gcd (|w|, |z|). Detailed improvements of this result are also proven. Finally, we show that each primitive word w has a conjugate w′ = vu, where w = uv, such that π(w′) = |w′| and |u| < π(w). As a corollary we give a short proof of the fact that if u,v,w are words such that u ² is a prefix of v ², and v ² is a prefix of w ², and v is primitive, then |w| > 2|u|.     

Sleeping on the Job: Energy-Efficient and Robust Broadcast for Radio Networks

We address the problem of minimizing power consumption when broadcasting a message from one node to all the other nodes in a radio network. To enable power savings for such a problem, we introduce a compelling new data streaming problem which we call the Bad Santa problem. Our results on this problem apply for any situation where: (1) a node can listen to a set of n nodes, out of which at least half are non-faulty and know the correct message; and (2) each of these n nodes sends according to some predetermined schedule which assigns each of them its own unique time slot. In this situation, we show that in order to receive the correct message with probability 1, it is necessary and sufficient for the listening node to listen to a \(\Theta(\sqrt{n})\) expected number of time slots. Moreover, if we allow for repetitions of transmissions so that each sending node sends the message O(log?^? n) times (i.e. in O(log?^? n) rounds each consisting of the n time slots), then listening to O(log?^? n) expected number of time slots suffices. We show that this is near optimal.We describe an application of our result to the popular grid model for a radio network. Each node in the network is located on a point in a two dimensional grid, and whenever a node sends a message m, all awake nodes within L _∞ distance r receive m. In this model, up to \(t<\frac{r}{2}(2r+1)\) nodes within any 2r+1 by 2r+1 square in the grid can suffer Byzantine faults. Moreover, we assume that the nodes that suffer Byzantine faults are chosen and controlled by an adversary that knows everything except for the random bits of each non-faulty node. This type of adversary models worst-case behavior due to malicious attacks on the network; mobile nodes moving around in the network; or static nodes losing power or ceasing to function. Let n=r(2r+1). We show how to solve the broadcast problem in this model with each node sending and receiving an expected \(O(n\log^{2}{|m|}+\sqrt{n}|m|)\) bits where |m| is the number of bits in m, and, after broadcasting a fingerprint of m, each node is awake only an expected \(O(\sqrt{n})\) time slots. Moreover, for t≤(1?ε)(r/2)(2r+1), for any constant ε>0, we can achieve an even better energy savings. In particular, if we allow each node to send O(log?^? n) times, we achieve reliable broadcast with each node sending O(nlog?²|m|+(log?^? n)|m|) bits and receiving an expected O(nlog?²|m|+(log?^? n)|m|) bits and, after broadcasting a fingerprint of m, each node is awake for only an expected O(log?^? n) time slots. Our results compare favorably with previous protocols that required each node to send Θ(|m|) bits, receive Θ(n|m|) bits and be awake for Θ(n) time slots.     

New results on the time complexity and approximation ratio of the Broadcast Incremental Power algorithm

The Broadcast Incremental Power (BIP) algorithm is the most frequently cited method for the minimum energy broadcast routing problem. A recent survey concluded that BIP has O(³|V|) time complexity, and that its approximation ratio is at least 4.33. We strengthen these results to O(²|V|) and 4.598, respectively.     

Efficiently Storing Well-Composed Polyhedral Complexes Computed Over 3D Binary Images

A 3D binary image I can be naturally represented by a combinatorial-algebraic structure called cubical complex and denoted by Q(I), whose basic building blocks are vertices, edges, square faces and cubes. In Gonzalez-Diaz et al. (Discret Appl Math 183:59–77, 2015), we presented a method to “locally repair” Q(I) to obtain a polyhedral complex P(I) (whose basic building blocks are vertices, edges, specific polygons and polyhedra), homotopy equivalent to Q(I), satisfying that its boundary surface is a 2D manifold. P(I) is called a well-composed polyhedral complex over the picture I. Besides, we developed a new codification system for P(I), encoding geometric information of the cells of P(I) under the form of a 3D grayscale image, and the boundary face relations of the cells of P(I) under the form of a set of structuring elements. In this paper, we build upon (Gonzalez-Diaz et al. 2015) and prove that, to retrieve topological and geometric information of P(I), it is enough to store just one 3D point per polyhedron and hence neither grayscale image nor set of structuring elements are needed. From this “minimal” codification of P(I), we finally present a method to compute the 2-cells in the boundary surface of P(I).     

Efficient generation of the ideals of a poset in Gray code order

Preusse and Ruskey [G. Pruesse, F. Ruskey, Gray codes from antimatroids, Order 10 (1993) 239-252] presented an algorithm for generating a Gray code for the ideals of a poset, where two adjacent ideals differ by one or two elements. Their algorithm takes O(n) amortized time per ideal. Squire [M. Squire, Enumerating the ideals of a poset, http://citeseer.ist.psu.edu/465417.html] presented a recurrence for the ideals of a poset that enabled him to find an algorithm for generating these ideals in O(logn) amortized time per ideal, but not in Gray code order. We use Squire's recurrence to find a Gray code for the ideals of a poset, where two adjacent ideals differ by one or two elements. In the worst case our algorithm has the same complexity as that of Pruesse and Ruskey and in the other cases its complexity is better and approaches that of Squire's algorithm.     

Minmax scheduling with acceptable lead-times: Extensions to position-dependent processing times,due-window and job rejection

We focus on a due-date assignment model where due-dates are determined by penalties for jobs exceeding pre-specified (job-dependent, different) deadlines. The underlying assumption of this model, denoted by DIF, is that there are "lead times that customers consider to be reasonable and expected". In a minmax DIF model, the value of the objective function is that of the largest job/due-date cost. The goal is to find both the job sequence and the due-dates, such that this value is minimized.In this paper we study several extensions of the minmax DIF model. First, we consider general position-dependent job processing times. Then we extend the model to a setting of a due-window for acceptable lead-times. Here, the assumption is that a time interval exists, such that due-dates assigned to be within this interval are not penalized. The last extension of the DIF model is to a setting allowing job-rejection. This option reflects many real-life situations, where the scheduler may decide to process only a subset of the jobs, and the rejected jobs are penalized. The first two extensions are shown to be polynomially solvable: we introduce solution algorithms requiring O(n³) and O(n⁴) time, respectively, where n is the number of jobs. The last extension (assuming job-rejection) is proved to be NP-hard in the ordinary sense, and an efficient pseudo-polynomial dynamic programming algorithm is introduced.     

Optimal parallel detection of squares in strings

A stringw isprimitive if it is not a power of another string (i.e., writingw =v ^k impliesk = 1. Conversely,w is asquare ifw =vv, withv a primitive string. A stringx issquare-free if it has no nonempty substring of the formww. It is shown that the square-freedom of a string ofn symbols over an arbitrary alphabet can be tested by a CRCW PRAM withn processors inO(logn) time and linear auxiliary space. If the cardinality of the input alphabet is bounded by a constant independent of the input size, then the number of processors can be reduced ton/logn without affecting the time complexity of this strategy. The fastest sequential algorithms solve this problemO(n logn) orO(n) time, depending on whether the cardinality of the input alphabet is unbounded or bounded, and either performance is known to be optimal within its class. More elaborate constructions lead to a CRCW PRAM algorithm for detecting, within the samen-processors bounds, all positioned squares inx in timeO(logn) and using linear auxiliary space. The fastest sequential algorithms solve this problem inO(n logn) time, and such a performance is known to be optimal.     

A $${\mathcal{O}(|G|n^6)}$$ time extension of inversion transduction grammars

Range concatenation grammars are viewed as a hierarchy of synchronous grammars. It is shown how inversion transduction grammars (ITGs) and extensions thereof, including synchronous tree-adjoining grammars, are captured by the hierarchy, and the expressivity and linguistic relevance of subclasses of the hierarchy are discussed. A O(|G|n⁶){\mathcal{O}(|G|n^6)} time extension of ITGs is proposed. The extension translates cross-serial dependencies into nested ones and handles complex kinds of discontinuous translation units and so-called inside-out alignments. In fact, our O(|G|n⁶){\mathcal{O}(|G|n^6)} time extension generates all possible alignments. It is shown that this additional expressivity comes at the cost of probabilistic parsing.     

One-Way Functions Using Algorithmic and Classical Information Theories

We prove several results relating injective one-way functions, time-bounded conditional Kolmogorov complexity, and time-bounded conditional entropy. First we establish a connection between injective, strong and weak one-way functions and the expected value of the polynomial time-bounded Kolmogorov complexity, denoted here by?E(K ^t (x|f(x))). These results are in both directions. More precisely, conditions on?E(K ^t (x|f(x))) that imply that?f is a weak one-way function, and properties of?E(K ^t (x|f(x))) that are implied by the fact that?f is a strong one-way function. In particular, we prove a separation result: based on the concept of time-bounded Kolmogorov complexity, we find an interval in which every function?f is a necessarily weak but not a strong one-way function. Then we propose an individual approach to injective one-way functions based on Kolmogorov complexity, defining Kolmogorov one-way functions and prove some relationships between the new proposal and the classical definition of one-way functions, showing that a Kolmogorov one-way function is also a deterministic one-way function. A relationship between Kolmogorov one-way functions and the conjecture of polynomial time symmetry of information is also proved. Finally, we relate?E(K ^t (x|f(x))) and two forms of time-bounded entropy, the unpredictable entropy?H ^unp, in which ??one-wayness?? of a function can be easily expressed, and the Yao⁺ entropy, a measure based on compression/decompression schema in which only the decompressor is restricted to be time-bounded.     

An optimal arc consistency algorithm for a particular case of sequence constraint

The AtMostSeqCard constraint is the conjunction of a cardinality constraint on a sequence of n variables and of n???q?+?1 constraints AtMost u on each subsequence of size q. This constraint is useful in car-sequencing and crew-rostering problems. In van Hoeve et al. (Constraints 14(2):273–292, 2009), two algorithms designed for the AmongSeq constraint were adapted to this constraint with an O(2 ^q n) and O(n ³) worst case time complexity, respectively. In Maher et al. (2008), another algorithm similarly adaptable to filter the AtMostSeqCard constraint with a time complexity of O(n ²) was proposed. In this paper, we introduce an algorithm for achieving arc consistency on the AtMostSeqCard constraint with an O(n) (hence optimal) worst case time complexity. Next, we show that this algorithm can be easily modified to achieve arc consistency on some extensions of this constraint. In particular, the conjunction of a set of m AtMostSeqCard constraints sharing the same scope can be filtered in O(nm). We then empirically study the efficiency of our propagator on instances of the car-sequencing and crew-rostering problems.     

Two-layer channel routing with vertical unit-length overlap

We show that anyn-net 2-terminal channel routing problem of densityd can be wired on a two-layer grid of widthw =d +O(d ^2/3) when vertical wire segments are allowed to overlap for a distance of length 1. This is a considerable asymptotic improvement over the best known, and optimal, channel width of 2d-1 for models in which no vertical overlap is allowed [RBM, PL]. Our result also improves the 3d/2+O(1) channel width achieved by a recent algorithm [G] for the same vertical overlap model. The algorithm presented in this paper produces at most 4 overlaps of unit length between any two nets, usesO(n) contacts, and can be implemented to run inO(nd ^2/3) time. We also generalize the algorithm to multi-terminal channel routing problems for which our algorithm uses a width ofw = 2d +O(d ^2/3).     

A Randomized Sieving Algorithm for Approximate Integer Programming

The Integer Programming Problem (IP) for a polytope \(P \subseteq \mathbb{R} ^{n}\) is to find an integer point in P or decide that P is integer free. We give a randomized algorithm for an approximate version of this problem, which correctly decides whether P contains an integer point or whether a (1+?)-scaling of P about its center of gravity is integer free in 2 ^O(n)(1/? ²) ⁿ -time and 2 ^O(n)(1/?) ⁿ -space with overwhelming probability. Our algorithm proceeds by reducing the approximate IP problem to an approximate Closest Vector Problem (CVP) under a “near-symmetric” norm. Our main technical contribution is an extension of the AKS randomized sieving technique, first developed by Ajtai et al. (Proceedings of 33rd Symposium on the Theory of Computing (STOC), pp. 601–610, 2001) for lattice problems under the ? ₂ norm, to the setting of asymmetric norms. We also present an application of our techniques to exact IP, where we give a nearly optimal algorithmic implementation of the Flatness Theorem, a central ingredient for many IP algorithms. Our results also extend to general convex bodies and lattices.     

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.     

The efficiency of the alpha-beta search on trees with branch-dependent terminal node scores

An analysis of the efficiency of the alpha-beta algorithm is carried out based on a probabilistic model in which terminal node scores depend on random branch values. Explicit expressions are derived for the expected number of terminal nodes scored for the cases of uniform trees of fanout N and of depths 2 and 3. For trees of depth 2, the expected number is of order O(NH_N); for trees of depth 3, the expected number is of order O(N²). An upper bound on the expected number of terminal nodes scored for trees of depth 4 is shown to be no greater than O(N²H_N²) and no less than O(N²).     

A new factorization of the mass matrix for optimal serial and parallel calculation of multibody dynamics

This paper describes a new factorization of the inverse of the joint-space inertia matrix M. In this factorization, M ^?1 is directly obtained as the product of a set of sparse matrices wherein, for a serial chain, only the inversion of a block-tridiagonal matrix is needed. In other words, this factorization reduces the inversion of a dense matrix to that of a block-tridiagonal one. As a result, this factorization leads to both an optimal serial and an optimal parallel algorithm, that is, a serial algorithm with a complexity of O(N) and a parallel algorithm with a time complexity of O(logN) on a computer with O(N) processors. The novel feature of this algorithm is that it first calculates the interbody forces. Once these forces are known, the accelerations are easily calculated. We discuss the extension of the algorithm to the task of calculating the forward dynamics of a kinematic tree consisting of a single main chain plus any number of short side branches. We also show that this new factorization of M ^?1 leads to a new factorization of the operational-space inverse inertia, Λ ^?1, in the form of a product involving sparse matrices. We show that this factorization can be exploited for optimal serial and parallel computation of Λ ^?1, that is, a serial algorithm with a complexity of O(N) and a parallel algorithm with a time complexity of O(logN) on a computer with O(N) processors.     

A linear time algorithm for finding an optimal degree-bounded subtree of an edge-weighted tree

Given an edge-weighted tree T=(V(T),E(T)) and its subtree T^′, for any v∈V(T), the distance d(v,T^′) is defined as the minimum weighted distance from v to any vertex in T^′. The distance d(T,T^′) is defined as the sum of all distances of the form d(v,T^′) where v∈V(T). We give an algorithm to find a T^′ that minimizes d(T,T^′) and for all w∈V(T^′), the degree degT^′(w) of w is not more than a prespecified bound db(w)(0?db(w)?degT(w)) at w. The worst-case running time of our algorithm is in O(|V(T)|).