Abstract: 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 \text{fnAM} and therefore is not \NP-hard ( \NP $\not \subseteq \Ptime^{\text{GroupRA}}$) 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 ($\Sigma\Pi\Sigma$ circuits). We give the first deterministic polynomial time identity test for $\depthT$ circuits with bounded top fanin.

Next, we consider the deterministic complexity of the problem of polynomial factorization over finite fields - given a finite field $\FF_q$ and a polynomial $h(x, y) \in \FF_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 {\em 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 $\FF_q$ and a set of polynomials $f_1, f_2, \cdots , f_m \in \FF_q[x_1, x_2, \cdots , x_n]$ of total degree at most $d$ determine the $\FF_q$-solvability of the system $f_1 = f_2 = \cdots = 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 {\em 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 \cdot \log m \cdot \log q) $ and size $\Poly(d \cdot m \cdot \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.

Table of Contents

1. Introduction
2. Preliminaries
3. Automorphisms of Rings
4. Polynomial Identity Testing for Depth-3 Cicuits
5. Factoring Multivariate Polynomials over Finite Fields
6. Solvability of Polynomial Equations over Finite Fields
7. A blackbox derandomization of Primality Testing
8. Conjectures and Open Problems