Zohar Karnin, Amir Shpilka

In this paper we consider the problem of determining whether an

unknown arithmetic circuit, for which we have oracle access,

computes the identically zero polynomial. Our focus is on depth-3

circuits with a bounded top fan-in. We obtain the following

results.

1. A quasi-polynomial time deterministic black-box identity testing algorithm ... more >>>

Gábor Ivanyos, Marek Karpinski, Nitin Saxena

In this work we relate the deterministic

complexity of factoring polynomials (over

finite

fields) to certain combinatorial objects we

call

m-schemes. We extend the known conditional

deterministic subexponential time polynomial

factoring algorithm for finite fields to get an

underlying m-scheme. We demonstrate ...
more >>>

Vishwas Bhargava, Gábor Ivanyos, Rajat Mittal, Nitin Saxena

Constructing $r$-th nonresidue over a finite field is a fundamental computational problem. A related problem is to construct an irreducible polynomial of degree $r^e$ (where $r$ is a prime) over a given finite field $\F_q$ of characteristic $p$ (equivalently, constructing the bigger field $\F_{q^{r^e}}$). Both these problems have famous randomized ... more >>>

Ashish Dwivedi, Rajat Mittal, Nitin Saxena

Finding an irreducible factor, of a polynomial $f(x)$ modulo a prime $p$, is not known to be in deterministic polynomial time. Though there is such a classical algorithm that {\em counts} the number of irreducible factors of $f\bmod p$. We can ask the same question modulo prime-powers $p^k$. The irreducible ... more >>>

Ashish Dwivedi, Nitin Saxena

Igusa's local zeta function $Z_{f,p}(s)$ is the generating function that counts the number of integral roots, $N_{k}(f)$, of $f(\mathbf x) \bmod p^k$, for all $k$. It is a famous result, in analytic number theory, that $Z_{f,p}$ is a rational function in $\mathbb{Q}(p^s)$. We give an elementary proof of this fact ... more >>>