Dimension Extractors and Optimal Decompression

A dimension extractor is an algorithm designed to increase the effective dimension—i.e., the amount of computational randomness—of an infinite binary sequence, in order to turn a “partially random” sequence into a “more random” sequence. Extractors are exhibited for various effective dimensions, including constructive, computable, space-bounded, time-bounded, and finite-state dimension. Using similar techniques, the Ku?era-Gács theorem is examined from the perspective of decompression, by showing that every infinite sequence S is Turing reducible to a Martin-Löf random sequence R such that the asymptotic number of bits of R needed to compute n bits of S, divided by n, is precisely the constructive dimension of S, which is shown to be the optimal ratio of query bits to computed bits achievable with Turing reductions. The extractors and decompressors that are developed lead directly to new characterizations of some effective dimensions in terms of optimal decompression by Turing reductions.     

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.     

Maintaining B-Trees on an EREW PRAM

Efficient and practical algorithms for maintaining general B-trees on an EREW PRAM are presented. Given a B-tree of order b with m distinct records, the search (respectively, insert and delete) problem for n input keys is solved on an n-processor EREW PRAM in O(log n + b log_b m) (respectively, O(b(log n + log_b m)) and O(b²(log_b n + log_b m))) time.     

Approximate Solutions of Polynomial Equations

In this paper, we introduce “approximate solutions" to solve the following problem: given a polynomial F(x, y) over Q, where x represents an n -tuple of variables, can we find all the polynomials G(x) such that F(x, G(x)) is identically equal to a constant c in Q ? We have the following: let F(x, y) be a polynomial over Q and the degree of y in F(x, y) be n. Either there is a unique polynomial g(x)  ∈ Q [ x ], with its constant term equal to 0, such that F(x, y)  = ∑_j = 0ⁿc_j(y − g(x))^jfor some rational numbers c_j, hence, F(x, g(x)  + a)  ∈ Q for all a ∈ Q, or there are at most t distinct polynomials g₁(x),⋯ , g_t(x), t ≤ n, such that F(x, g_i(x))  ∈ Q for 1  ≤ i ≤ t. Suppose that F(x, y) is a polynomial of two variables. The polynomial g(x) for the first case, or g₁(x),⋯ , g_t(x) for the second case, are approximate solutions of F(x, y), respectively. There is also a polynomial time algorithm to find all of these approximate solutions. We then use Kronecker’s substitution to solve the case of F(x, y).     

An approximation method for high-order fractional derivatives of algebraically singular functions

The fractional derivative D^qf(s) (0≤s≤1) of a given function f(s) with a positive non-integer q is defined in terms of an indefinite integral. We propose a uniform approximation scheme to D^qf(s) for algebraically singular functions f(s)=s^αg(s) (α>−1) with smooth functions g(s). The present method consists of interpolating g(s) at sample points t_j in [0,1] by a finite sum of the Chebyshev polynomials. We demonstrate that for the non-negative integer m such that m<q<m+1, the use of high-order derivatives g⁽ⁱ⁾(0) and g⁽ⁱ⁾(1) (0≤i≤m) at both ends of [0,1] as well as g(t_j), t_j∈[0,1] in interpolating g(s), is essential to uniformly approximate D^q{s^αg(s)} for 0≤s≤1 when α≥q−m−1. Some numerical examples in the simplest case 1<q<2 are included.     

Geometric pattern matching for point sets in the plane under similarity transformations

We consider the following geometric pattern matching problem: Given two sets of points in the plane, P and Q, and some (arbitrary) δ>0, find a similarity transformation T (translation, rotation and scale) such that h(T(P),Q)<δ, where h(⋅,⋅) is the directional Hausdorff distance with L_∞ as the underlying metric; or report that none exists. We are only interested in the decision problem, not in minimizing the Hausdorff distance, since in the real world, where our applications come from, δ is determined by the practical uncertainty in the position of the points (pixels). Similarity transformations have not been dealt with in the context of the Hausdorff distance and we fill the gap here. We present efficient algorithms for this problem imposing a reasonable separation restriction on the points in the set Q. If the L_∞ distance between every pair of points in Q is at least 8δ, then the problem can be solved in O(mn²logn) time, where m and n are the numbers of points in P and Q respectively. If the L_∞ distance between every pair of points in Q is at least cδ, for some c, 0<c<1, we present a randomized approximate solution with expected runtime O(n²c−4ε−8log⁴mn), where ε>0 controls the approximation. Our approximation is on the size of the subset, B⊆P, such that h(T(B),Q)<δ and |B|>(1−ε)|P| with high probability.     

Evaluation and comparison of two efficient probabilistic primality testing algorithms

We analyse two recent probabilistic primality testing algorithms; the first one is derived from Miller [6] in a formulation given by Rabin [7], and the second one is from Solovay and Strassen [9]. Both decide whether or not an odd number n is prime in time O(m, lognM(n)) with an error probability less than α^m, for some $\text{0≤a<}\text{1}\text{2}$. Our comparison shows that the first algorithm is always more efficient than the second, both in probabilistic and algorithmic terms.     

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)).     

A Cubic-Vertex Kernel for Flip Consensus Tree

Given a bipartite graph G=(V _c ,V _t ,E) and a nonnegative integer k, the NP-complete Minimum-Flip Consensus Tree problem asks whether G can be transformed, using up to k edge insertions and deletions, into a graph that does not contain an induced P ₅ with its first vertex in V _t (a so-called M-graph or Σ-graph). This problem plays an important role in computational phylogenetics, V _c standing for the characters and V _t standing for taxa. Chen et al. (IEEE/ACM Trans. Comput. Biol. Bioinform. 3:165–173, 2006). showed that Minimum-Flip Consensus Tree is NP-complete and presented a parameterized algorithm with running time O(6 ^k ?|V _t |?|V _c |). Subsequently, Böcker et al. (ACM Trans. Algorithms 8:7:1–7:17, 2012) presented a refined search tree algorithm with running time O(4.42 ^k (|V _t |+|V _c |)+|V _t |?|V _c |). We continue the study of Minimum-Flip Consensus Tree parameterized by k. Our main contribution are polynomial-time executable data reduction rules yielding a problem kernel with O(k ³) vertices. In addition, we present an improved search tree algorithm with running time O(3.68 ^k ?|V _c |²|V _t |).     

Shorthand Universal Cycles for Permutations

The set of permutations of ??n??={1,??,n} in one-line notation is ??(n). The shorthand encoding of a ₁?a _n ????(n) is a ₁?a _n?1. A shorthand universal cycle for permutations (SP-cycle) is a circular string of length n! whose substrings of length n?1 are the shorthand encodings of ??(n). When an SP-cycle is decoded, the order of ??(n) is a Gray code in which successive permutations differ by the prefix-rotation ?? _i =(1 2 ? i) for i??{n?1,n}. Thus, SP-cycles can be represented by n! bits. We investigate SP-cycles with maximum and minimum ??weight?? (number of ?? _n?1s in the Gray code). An SP-cycle n a n b?n z is ??periodic?? if its ??sub-permutations?? a,b,??,z equal ??(n?1). We prove that periodic min-weight SP-cycles correspond to spanning trees of the (n?1)-permutohedron. We provide two constructions: B(n) and C(n). In B(n) the spanning trees use ??half-hunts?? from bell-ringing, and in C(n) the sub-permutations use cool-lex order by Williams (SODA, 987?C996, 2009). Algorithmic results are: (1)?memoryless decoding of B(n) and C(n), (2)?O((n?1)!)-time generation of B(n) and C(n) using sub-permutations, (3)?loopless generation of B(n)??s binary representation n bits at a time, and (4)?O(n+??(n))-time ranking of B(n)??s permutations where ??(n) is the cost of computing a permutation??s inversion vector. Results (1)?C(4) improve on those for the previous SP-cycle construction D(n) by Ruskey and Williams (ACM Trans. Algorithms 6(3):Art.?45, 2010), which we characterize here using ??recycling??.     

Speeding up transposition-invariant string matching

Finding the longest common subsequence (LCS) of two given sequences A=a₀a₁…am−1 and B=b₀b₁…bn−1 is an important and well studied problem. We consider its generalization, transposition-invariant LCS (LCTS), which has recently arisen in the field of music information retrieval. In LCTS, we look for the LCS between the sequences A+t=(a₀+t)(a₁+t)…(am−1+t) and B where t is any integer. We introduce a family of algorithms (motivated by the Hunt-Szymanski scheme for LCS), improving the currently best known complexity from O(mnloglogσ) to O(Dloglogσ+mn), where σ is the alphabet size and D?mn is the total number of dominant matches for all transpositions. Then, we demonstrate experimentally that some of our algorithms outperform the best ones from literature.     

New compacton soliton solutions and solitary patterns solutions of nonlinearly dispersive Boussinesq equations

The special exact solutions of nonlinearly dispersive Boussinesq equations (called B(m,n) equations), u_tt−u_xx−a(uⁿ)_xx+b(u^m)_xxxx=0, is investigated by using four direct ansatze. As a result, abundant new compactons: solitons with the absence of infinite wings, solitary patterns solutions having infinite slopes or cups, solitary waves and singular periodic wave solutions of these two equations are obtained. The variant is extended to include linear dispersion to support compactons and solitary patterns in the linearly dispersive Boussinesq equations with m=1. Moreover, another new compacton solution of the special case, B(2,2) equation, is also found.     

Positively invariant sets of discrete-time systems with constrained inputs

Linear discrete-time dynamical systems x_k + _I = Ax_k + _k with constrained inputs c_k ∈ ω, for which the matrix A possesses the property of leaving a proper cone AK + positively invariant, i.e. AK + ? K + . Necessary and sufficient conditions guarantee that a non-empty set 𝒟(K; a, b) ? Rⁿ, obtained from the intersection of translated proper cones, is positively invariant for motions of the system. Both the homogeneous and inhomogeous cases are considered. In the latter case, the external behaviour of motions, i.e. for trajectories originating from x₀ ? Rⁿ/𝒟(K; a, b) (respectively,x_o ? Rⁿ) is studied in terms of attractive and contractivity of the set 𝒟(K; a, b). The global attractivity conditions of 𝒟(K; a, b) are also given. It is shown how the results presented can be used to solve the saturated state feedback regulator problem.     

Cache-oblivious index for approximate string matching

This paper revisits the problem of indexing a text for approximate string matching. Specifically, given a text T of length n and a positive integer k, we want to construct an index of T such that for any input pattern P, we can find all its k-error matches in T efficiently. This problem is well-studied in the internal-memory setting. Here, we extend some of these recent results to external-memory solutions, which are also cache-oblivious. Our first index occupies O((nlog^kn)/B) disk pages and finds all k-error matches with O((|P|+occ)/B+log^knloglog_Bn) I/Os, where B denotes the number of words in a disk page. To the best of our knowledge, this index is the first external-memory data structure that does not require Ω(|P|+occ+poly(logn)) I/Os. The second index reduces the space to O((nlogn)/B) disk pages, and the I/O complexity is O((|P|+occ)/B+log^k(k+1)nloglogn).     

Construction of high degree resilient S-boxes with improved nonlinearity

We present a simple method to use an [n−d−1,m,t+1] code to construct an n-input, m-output, t-resilient function with degree d>m and nonlinearity ²n−1−²n−⌈(d+1)/2⌉−(m+1)²n−d−1. For any fixed values of parameters n,m,t and d, with d>m, the nonlinearity obtained by our construction is higher than the nonlinearity obtained by Cheon in Crypto 2001.     

Monotone separations for constant degree polynomials

We prove a separation between monotone and general arithmetic formulas for polynomials of constant degree. We give an example of a polynomial C in n variables and degree k which is computable by a homogeneous arithmetic formula of size O(k²n²), but every monotone formula computing C requires size (n/kc)^Ω(logk), with c∈(0,1). Since the upper bound is achieved by a homogeneous arithmetic formula, we also obtain a separation between monotone and homogeneous formulas, for polynomials of constant degree.     

On the qualitative behaviors of solutions of third order nonlinear differential equations

We present some new results about oscillation and asymptotic behavior of solutions of third order nonlinear differential equations of the form

(r₂(t)(r₁(t)y^′)^′)^′+p(t)y^′+q(t)f(y(g(t)))=0.     

Some new sequence spaces derived by the domain of the triple band matrix

Let λ denote any of the classical spaces ?_∞,c,c₀, and ?_p of bounded, convergent, null, and absolutely p-summable sequences, respectively, and let λ(B) also be the domain of the triple band matrix B(r,s,t) in the sequence space λ, where 1<p<∞. The present paper is devoted to studying the sequence space λ(B). Furthermore, the β- and γ-duals of the space λ(B) are determined, the Schauder bases for the spaces c(B), c₀(B), and ?_p(B) are given, and some topological properties of the spaces c₀(B), ?₁(B), and ?_p(B) are examined. Finally, the classes (λ₁(B):λ₂) and (λ₁(B):λ₂(B)) of infinite matrices are characterized, where λ₁∈{?_∞,c,c₀,?_p,?₁} and λ₂∈{?_∞,c,c₀,?₁}.     

Uniform computational complexity of the derivatives of C∞-functions

We discuss the uniform computational complexity of the derivatives of C^∞-functions in the model of Ko and Friedman (Ko, Complexity Theory of Real Functions, Birkhäuser, Basel, 1991; Ko, Friedman, Theor. Comput. Sci. 20 (1982) 323–352). We construct a polynomial time computable real function g∈C^∞[−1,1] such that the sequence $\text{{|g}{}^{\mathrm{(n)}}\text{(0)|}}{}_{\mathrm{<mtext>n\in </mtext><mtext>N</mtext>}}$ is not bounded by any recursive function. On the other hand, we show that if f∈C^∞[−1,1] is polynomial time computable and the sequence of the derivatives of f is uniformly polynomially bounded, i.e., |f⁽ⁿ⁾(x)| is bounded by 2^p(n) for all x∈[−1,1] for some polynomial p, then the sequence $\text{{f}{}^{\mathrm{(n)}}\text{}}{}_{\mathrm{<mtext>n\in </mtext><mtext>N</mtext>}}$ is uniformly polynomial time computable.     

A new subclass of cyclic Goppa codes

We propose a subclass of cyclic Goppa codes given by separable self-reciprocal Goppa polynomials of degree two. We prove that this subclass contains all reversible cyclic codes of length n, n | (q ^m ± 1), with a generator polynomial g(x), g(α ^±i ) = 0, i = 0, 1, α ⁿ = 1, α ∈ GF(q ^2m ).