We give new randomized algorithms for testing multivariate polynomial identities over finite fields and rationals. The algorithms use \lceil \sum_{i=1}^n \log(d_i+1)\rceil (plus \lceil\log\log C\rceil in case of rationals where C is the largest coefficient) random bits to test if a polynomial P(x_1, ..., x_n) is zero where d_i is the ... more >>>

We study the identity testing problem for depth $3$ arithmetic circuits ($\Sigma\Pi\Sigma$ circuits). We give the first deterministic polynomial time identity test for $\Sigma\Pi\Sigma$ circuits with bounded top fanin. We also show that the {\em rank} of a minimal and simple $\Sigma\Pi\Sigma$ circuit with bounded top fanin, computing zero, can ... more >>>

\begin{abstract} Given a monomial ideal $I=\angle{m_1,m_2,\cdots,m_k}$ where $m_i$ are monomials and a polynomial $f$ as an arithmetic circuit the \emph{Ideal Membership Problem } is to test if $f\in I$. We study this problem and show the following results. \begin{itemize} \item[(a)] If the ideal $I=\angle{m_1,m_2,\cdots,m_k}$ for a \emph{constant} $k$ then there ... more >>>

In this paper we give the first deterministic polynomial time algorithm for testing whether a {\em diagonal} depth-$3$ circuit $C(\arg{x}{n})$ (i.e. $C$ is a sum of powers of linear functions) is zero. We also prove an exponential lower bound showing that such a circuit will compute determinant or permanent only ... more >>>

We show that proving exponential lower bounds on depth four arithmetic circuits imply exponential lower bounds for unrestricted depth arithmetic circuits. In other words, for exponential sized circuits additional depth beyond four does not help. We then show that a complete black-box derandomization of Identity Testing problem for depth four ... more >>>

Let $\F\{x_1,x_2,\cdots,x_n\}$ be the noncommutative polynomial ring over a field $\F$, where the $x_i$'s are free noncommuting formal variables. Given a finite automaton $\A$ with the $x_i$'s as alphabet, we can define polynomials $\f( mod A)$ and $\f(div A)$ obtained by natural operations that we call \emph{intersecting} and \emph{quotienting} the ... more >>>

Polynomial identity testing (PIT) is the problem of checking whether a given arithmetic circuit is the zero circuit. PIT ranks as one of the most important open problems in the intersection of algebra and computational complexity. In the last few years, there has been an impressive progress on this problem ... more >>>

We give the first sub-exponential time deterministic polynomial identity testing algorithm for depth-$4$ multilinear circuits with a small top fan-in. More accurately, our algorithm works for depth-$4$ circuits with a plus gate at the top (also known as $\Spsp$ circuits) and has a running time of $\exp(\poly(\log(n),\log(s),k))$ where $n$ is ... more >>>

An \emph{arithmetic read-once formula} (ROF for short) is a formula (a circuit whose underlying graph is a tree) in which the operations are $\{+,\times\}$ and such that every input variable labels at most one leaf. A \emph{preprocessed ROF} (PROF for short) is a ROF in which we are allowed to ... more >>>