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.     

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.     

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

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.     

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.     

A deterministic test for permutation polynomials

A new deterministic algorithm is presented for testing whether a given polynomial of degreen over a finite field ofq elements is a permutation polynomial. The algorithm has computing time (nq)^6/7+, and gives a positive answer to a question of Lidl and Mullen.     

Liouvillian solutions of third order differential equations

The Kovacic algorithm and its improvements give explicit formulae for the Liouvillian solutions of second order linear differential equations. Algorithms for third order differential equations also exist, but the tools they use are more sophisticated and the computations more involved. In this paper we refine parts of the algorithm to find Liouvillian solutions of third order equations. We show that, except for four finite groups and a reduction to the second order case, it is possible to give a formula in the imprimitive case. We also give necessary conditions and several simplifications for the computation of the minimal polynomial for the remaining finite set of finite groups (or any known finite group) by extracting ramification information from the character table. Several examples have been constructed, illustrating the possibilities and limitations.     

Fast evaluation of vector splines in three dimensions

Vector spline techniques have been developed as general-purpose methods for vector field reconstruction. However, such vector splines involve high computational complexity, which precludes applications of this technique to many problems using large data sets. In this paper, we develop a fast multipole method for the rapid evaluation of the vector spline in three dimensions. The algorithm depends on a tree-data structure and two hierarchical approximations: an upward multipole expansion approximation and a downward local Taylor series approximation. In comparison with the CPU time of direct calculation, which increases at a quadratic rate with the number of points, the presented fast algorithm achieves a higher speed in evaluation at a linear rate. The theoretical error bounds are derived to ensure that the fast method works well with a specific accuracy. Numerical simulations are performed in order to demonstrate the speed and the accuracy of the proposed fast method.     

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

The complexity of computing maximal word functions

Maximal word functions occur in data retrieval applications and have connections with ranking problems, which in turn were first investigated in relation to data compression [21]. By the maximal word function of a languageL ^*, we mean the problem of finding, on inputx, the lexicographically largest word belonging toL that is smaller than or equal tox.In this paper we present a parallel algorithm for computing maximal word functions for languages recognized by one-way nondeterministic auxiliary pushdown automata (and hence for the class of context-free languages).This paper is a continuation of a stream of research focusing on the problem of identifying properties others than membership which are easily computable for certain classes of languages. For a survey, see [24].     

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.     

Retrieval of scattered information by EREW,CREW, and CRCW PRAMs

Thek-compaction problem arises whenk out ofn cells in an array are non-empty and the contents of these cells must be moved to the firstk locations in the array. Parallel algorithms fork-compaction have obvious applications in processor allocation and load balancing;k-compaction is also an important subroutine in many recently developed oped parallel algorithms. We show that any EREW PRAM that solves thek-compaction problem requires time, even if the number of processors is arbitrarily large andk=2. On the CREW PRAM, we show that everyn-processor algorithm fork-compaction problem requires (log logn) time, even ifk=2. Finally, we show thatO(logk) time can be achieved on the ROBUST PRAM, a very weak CRCW PRAM model.     

Characterising the Martin-Löf random sequences using computably enumerable sets of measure one

A sequence ω is Martin-Löf random if and only if it appears early in every Lebesgue measure one set of computably enumerable intervals.     

Non-deterministic exponential time has two-prover interactive protocols

We determine the exact power of two-prover interactive proof systems introduced by Ben-Or, Goldwasser, Kilian, and Wigderson (1988). In this system, two all-powerful noncommunicating provers convince a randomizing polynomial time verifier in polynomial time that the inputx belongs to the languageL. We show that the class of languages having tow-prover interactive proof systems is nondeterministic exponential time.We also show that to prove membership in languages inEXP, the honest provers need the power ofEXP only.The first part of the proof of the main result extends recent techniques of polynomial extrapolation used in the single prover case by Lund, Fortnow, Karloff, Nisan, and Shamir.The second part is averification scheme for multilinearity of a function in several variables held by an oracle and can be viewed as an independent result onprogram verification. Its proof rests on combinatorial techniques employing a simple isoperimetric inequality for certain graphs:     

The complexity of the max word problem and the power of one-way interactive proof systems

We study the complexity of the max word problem for matrices, a variation of the well-known word problem for matrices. We show that the problem is NP-complete, and cannot be approximated within any constant factor, unless P=NP. We describe applications of this result to probabilistic finite state automata, rational series andk-regular sequences. Our proof is novel in that it employs the theory of interactive proof systems, rather than a standard reduction argument. As another consequence of our results, we characterize NP exactly in terms ofone-way interactive proof systems.     

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.     

Extensions of MSO and the monadic counting hierarchy

In this paper, we study the expressive power of the extension of first-order logic by the unary second-order majority quantifier Most¹. In 1 it was shown that the extension of FO by second-order majority quantifiers of all arities describes exactly the problems in the counting hierarchy. We consider first certain sublogics of FO(Most¹) over unary vocabularies. We show that over unary vocabularies the logic MSO(R), where MSO is monadic second-order logic and R is the first-order Rescher quantifier, can be characterized by Presburger arithmetic, whereas the logic MSO(Rⁿ)_n∈Z+, where Rⁿ is the nth vectorization of R, corresponds to the Δ₀-fragment of arithmetic. Then we show that FO(Most¹)?MSO(Rⁿ)_n∈Z+ and that, on unary vocabularies, FO(Most¹) collapses to uniform-TC⁰. Using this collapse, we show that first-order logic with the binary second-order majority quantifier is strictly more expressive than FO(Most¹) over the empty vocabulary. On the other hand, over strings, FO(Most¹) is shown to capture the linear fragment of the counting hierarchy. Finally we show that, over non-unary vocabularies, FO(Most¹) can express problems complete via first-order reductions for each level of the counting hierarchy.     

Fast exponentiation by folding the signed-digit exponent in half

For modern cryptographic systems, the public key cryptosystem such as RSA requires modular exponentiation (M ^E mod?N). The M, E and N are either as large as the 1024-bit integers or even larger, it is not a very good idea to directly compute M ^E mod?N. Recently, there are many techniques have been invented to solve the time-consuming computations of such time-consuming modular exponentiation. Among these useful algorithms, the “binary (square-and-multiply) algorithm” reduces the amount of modulo multiplications. As the “signed-digit representation algorithm” has the property of the nonzero digit occurrence probability equals to 1/3, taking this advantage, this method can more effectively decrease the amount of modular multiplications. Moreover, by using the technique of recording the common parts in the folded substrings, the “folding-exponent algorithm” can improve the efficiency of the binary algorithm, thus can further decrease the computational complexity of modular exponentiation. In this paper, a new modular exponentiation algorithm is proposed which based on the binary algorithm, signed-digit representation, and the folding-exponent technique. By using the parallel processing technique, in our proposed method, the modular multiplications and modular squaring can be executed in parallel, and thus lower down the computational complexity to k?+?3 multiplications. As modular squaring operation over GF(2 ⁿ ) is carried out by a simple cyclic right shift operation, the computational complexity of our proposed method can be further reduced to 29k/36?+?3 multiplications.