Derandomizing some algebraic and number-theoretic algorithms

The aim of this thesis is to provide deterministic upper bounds for various naturally occuring computational problems. We begin this thesis with a study of computational problems related to rings and their automorphisms. We consider the problem GroupRA of computing the automorhism group of a given ring in terms of a set of generators of its automorphism group. We show that an efficient deterministic algorithm for GroupRA would imply the existence of efficient deterministic algorithms for a number of well-studied problems of intermediate complexity including polynomial factoring (over finite fields), Integer factoring and Graph Isomorphism. On the other hand, we upper bound the complexity of GroupRA by showing that GroupRA is in the complexity class AM and therefore is not NP-hard unless the polynomial hierarchy collapses. We then consider the problem of computing a nontrivial automorphism of a given ring R and show that it is random-polynomial-time equivalent to integer factoring. We then investigate the complexity of determining the existence of a nontrivial automorphism of a given ring. This problem is shown to admit an efficient deterministic algorithm. We then study the identity testing problem for depth 3 arithmetic circuits (Sum-Product-Sum circuits). We give the first deterministic polynomial time identity test for depth three circuits with bounded top fanin. Next, we consider the deterministic complexity of the problem of polynomial factorization over finite fields – given a finite field F_q and  polynomial h(x, y) in F_q[x, y] compute a nontrivial factor of h(x, y). This problem admits a randomized polynomial-time algorithm and no deterministic polynomial-time algorithm is known. We give a deterministic polynomial-time algorithm that partially factors the input polynomial h(x, y). The motivation for the partial factoring algorithm developed is to upper bound the complexity of the following polynomial solvability problem: given a finite field F_q and a set of polynomials f₁, f₂, .. , f_m in F_q[x₁, .. , x_n]$ of total degree at most d determine the F_q-solvability of the system f₁ = f₂ = .. = f_m = 0. This problem is easily seen to be NP-complete even when the field size q is as small as 2 and the degree of each polynomial is bounded by d=2. Here we investigate the deterministic complexity of this problem when the number of variables n in the input is bounded. We show that there is a deterministic algorithm for this problem whose running time, for any fixed n, is bounded by a polynomial in d, m and log q. Moreover, the algorithm can be implemented parallely to get a family of Ptime-uniform circuits of depth poly(log d log m log q) and size poly(d m log q) for the solvability problem. Finally, we present a deterministic polynomial-time algorithm that determines whether an input number n is prime or composite.