Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with deterministic:
TR07-042 | 7th May 2007
Zohar Karnin, Amir Shpilka

Black Box Polynomial Identity Testing of Depth-3 Arithmetic Circuits with Bounded Top Fan-in

Revisions: 2 , Comments: 1

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

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

TR08-043 | 12th April 2008
Gábor Ivanyos, Marek Karpinski, Nitin Saxena

Schemes for Deterministic Polynomial Factoring

In this work we relate the deterministic
complexity of factoring polynomials (over
fields) to certain combinatorial objects we
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 >>>

TR17-016 | 31st January 2017
Vishwas Bhargava, Gábor Ivanyos, Rajat Mittal, Nitin Saxena

Irreducibility and deterministic r-th root finding over finite fields

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

TR19-033 | 20th February 2019
Ashish Dwivedi, Rajat Mittal, Nitin Saxena

Counting basic-irreducible factors mod $p^k$ in deterministic poly-time and $p$-adic applications

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

TR20-092 | 16th June 2020
Ashish Dwivedi, Nitin Saxena

Computing Igusa's local zeta function of univariates in deterministic polynomial-time

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

ISSN 1433-8092 | Imprint