Improving known solutions is hard

In this paper, we study the complexity of computing better solutions to optimization problems given other solutions. We use a model of computation suitable for this purpose, the counterexample computation model. We first prove that, if PH _P ³ , polynomial time transducers cannot compute optimal solutions for many problems, even givenn ^1– non-trivial solutions, for any >0. These results are then used to establish sharp lower bounds for several problems in the counterexample model. We extend the model by defining probabilistic counterexample computations and show that our results hold even in the presence of randomness.     

Circuits constructed with MOD q gates cannot compute “AND” in sublinear size

Algebraic techniques are used to prove that any circuit constructed with MOD _q gates that computes the AND function must use (n) gates at the first level. The best bound previously known to be valid for arbitraryq was (logn).     

Efficient and optimal exponentiation in finite fields

Optimal sequential and parallel algorithms for exponentiation in a finite field containing F _q are presented, assuming thatqth powers can be computed for free.     

Computing Frobenius maps and factoring polynomials

A new probabilistic algorithm for factoring univariate polynomials over finite fields is presented. To factor a polynomial of degreen overF _q , the number of arithmetic operations inF _q isO((n ²+nlogq). (logn)² loglogn). The main technical innovation is a new way to compute Frobenius and trace maps in the ring of polynomials modulo the polynomial to be factored.     

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.     

The computational complexity of recognizing permutation functions

Let be a finite field withq elements and a rational function over . No polynomial-time deterministic algorithm is known for the problem of deciding whetherf induces a permutation on . The problem has been shown to be in co-R co-NP, and in this paper we prove that it is inR NP and hence inZPP, and it is deterministic polynomial-time reducible to the problem of factoring univariate polynomials over . Besides the problem of recognizing prime numbers, it seems to be the only natural decision problem inZPP unknown to be inP. A deterministic test and a simple probabilistic test for permutation functions are also presented.     

Towards optimal simulations of formulas by bounded-width programs

We show that, over an arbitrary ring, for any fixed >0, all balanced algebraic formulas of sizes are computed by algebraic straight-line programs that employ a constant number of registers and have lengthO (s ¹⁺). In particular, in the special case where the ring isGF(2), we obtain a technique for simulating balanced Boolean formulas of sizes by bounded-width branching programs of lengthO(s ¹⁺), for any fixed >0. This is an asymptotic improvement in efficiency over previous simulations in both the Boolean and algebraic settings.     

On ACC

We show that every languageL in the class ACC can be recognized by depth-two deterministic circuits with a symmetric-function gate at the root and AND gates of fan-in log ^O(1) n at the leaves, or equivalently, there exist polynomialsp _n (x ₁ ,..., x _n ) overZ of degree log ^O(1) n and with coefficients of magnitude and functionsh _n :Z{0,1} such that for eachn and eachx{0,1} ⁿ ,XL ^(x) =h _n (p _n (x ₁ ,...,x _n )). This improves an earlier result of Yao (1985). We also analyze and improve modulus-amplifying polynomials constructed by Toda (1991) and Yao (1985).     

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.     

A storage scheme for extendible arrays

Conventional methods of storing aK-dimensional array allow easy extension only along one dimension. We present a technique of allocating a linear sequence of contiguous storage locations for aK-dimensional extendible array by adjoining blocks of (K–1)-dimensional subarrays. Element access is by determination of the block header location and then the displacement within the block. For cubical and all practical cases of rectangular arrays considered, the storage requirement isO (N) whereN is the array size. The element access cost isO (K) for the 2-step computed access function used.

---

Ein Speicherschema für erweiterbare Felder

Zusammenfassung Konventionelle Methoden der SpeicherungK-dimensionaler Felder lassen eine einfache Erweiterung lediglich entlang einer Dimension zu. Wir beschreiben eine Technik der Zuweisung einer linearen Folge von zusammenhängenden Speicherzellen fürK-dimensional erweiterbare Felder durch Hinzufügen von Blöcken aus (K–1)-dimensionierten Teilfeldern. Der Elementzugriff erfolgt durch Bestimmung des Headers und des Displacements innerhalb des Blockes. Für kubische und alle praktische Fälle rechteckiger Felder ist der SpeicherbedarfO (N) wobeiN die Feldgröße ist. Die Kosten eines Elementzugriffs betragenO (K) für die in zwei Schritten berechnete Zugriffsfunktion.

     

Non-oscillation of solutions of difference equations of third order

In this paper, sufficient conditions in terms of coefficient functions are obtained for non-oscillation of all solutions of a class of linear homogeneous third order difference equations of the form

     

Algorithmic properties of maximal orders in simple algebras over Q

This paper addresses an algorithmic problem related to associative algebras. We show that the problem of deciding if the index of a given central simple algebra over an algebraic number field isd, whered is a given natural number, belongs to the complexity classN P co N P. As consequences, we obtain that the problem of deciding if is isomorphic to a full matrix algebra over the ground field and the problem of deciding if is a skewfield both belong toN P co N P. These results answer two questions raised in [25]. The algorithms and proofs rely mostly on the theory of maximal orders over number fields, a noncommutative generalization of algebraic number theory. Our results include an extension to the noncommutative case of an algorithm given by Huang for computing the factorization of rational primes in number fields and of a method of Zassenhaus for testing local maximality of orders in number fields.     

Exact learning of DNF formulas using DNF hypotheses

We show the following: (a) For any ε>0, log^(3+ε)n-term DNF cannot be polynomial-query learned with membership and strongly proper equivalence queries. (b) For sufficiently large t, t-term DNF formulas cannot be polynomial-query learned with membership and equivalence queries that use t^1+ε-term DNF formulas as hypotheses, for some ε<1 (c) Read-thrice DNF formulas are not polynomial-query learnable with membership and proper equivalence queries. (d) logn-term DNF formulas can be polynomial-query learned with membership and proper equivalence queries. (This complements a result of Bshouty, Goldman, Hancock, and Matar that -term DNF can be so learned in polynomial time.)Versions of (a)-(c) were known previously, but the previous versions applied to polynomial-time learning and used complexity theoretic assumptions. In contrast, (a)-(c) apply to polynomial-query learning, imply the results for polynomial-time learning, and do not use any complexity-theoretic assumptions.     

Finding maximal orders in semisimple algebras over Q

We consider the algorithmic problem of constructing a maximal order in a semisimple algebra over an algebraic number field. A polynomial time ff-algorithm is presented to solve the problem. (An ffalgorithm is a deterministic method which is allowed to call oracles for factoring integers and for factoring polynomials over finite fields. The cost of a call is the size of the input given to the oracle.) As an application, we give a method to compute the degrees of the irreducible representations over an algebraic number fieldK of a finite groupG, in time polynomial in the discriminant of the defining polynomial ofK and the size of a multiplication table ofG.     

On the rank of certain finite fields

In the present paper we shall show that the rank of the finite field regarded as an -algebra has one of the two values 2n or 2n+1 ifn satisfies 1/2q+1<n<1/2(m(q)–2). Herem(q) denotes the maximum number of -rational points of an algebraic curve of genus 2 over . Using results of Davenport-Hasse, Honda and Rück we shall give lower bounds form(q) which are close to the Hasse-Weil bound . For specialq we shall further show thatm(q) is equal to the Hasse-Weil bound.     

On the existence and convergence of the solution of PML equations

In this article we study the mesh termination method in computational scattering theory known as the method of Perfectly Matched Layer (PML). This method is based on the idea of surrounding the scatterer and its immediate vicinity with a fictitious absorbing non-reflecting layer to damp the echoes coming from the mesh termination surface. The method can be formulated equivalently as a complex stretching of the exterior domain. The article is devoted to the existence and convergence questions of the solutions of the resulting equations. We show that with a special choice of the fictitious absorbing coefficient, the PML equations are solvable for all wave numbers, and as the PML layer is made thicker, the PML solution converge exponentially towards the actual scattering solution. The proofs are based on boundary integral methods and a new type of near-field version of the radiation condition, called here the double surface radiation condition. Partly supported by the Finnish Academy, project 37692.     

A generalisation of the Cantor-Zassenhaus algorithm

We generalise the Cantor-Zassenhaus algorithm for factoring polynomials over finite fields. The generalisation yields a class of factorisation algorithms. We compute their factorisation probability and their least upper bound. We then give a simple characterisation of the algorithms reaching the least upper bound. As an example we show the Cantor-Zassenhaus and the Ben-Or algorithms have a factorisation probability equal to the least upper bound.     

Algorithmic solution of Abel’s equation

The solution scheme for Abel’s equation proposed in this article avoids to a large extent thead hoc methods that have been discovered in the last two centuries since Abel introduced the equation named after him. On the one hand, it describes an algorithmic method for obtaining almost all closed form solutions known in the literature. It is based on Lie’s symmetry analysis. Secondly, for equations without a symmetry, a new method is proposed that allows to generate solutions of all equations within an equivalence class if a single representative has been solved before. It is based on functional decomposition of the absolute invariant of the equation at hand for which computer algebra algorithms have become available recently.