Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Nitin Saxena:

TR20-039 | 25th March 2020
Pranjal Dutta, Nitin Saxena, Thomas Thierauf

Lower bounds on the sum of 25th-powers of univariates lead to complete derandomization of PIT

We consider the univariate polynomial $f_d:=(x+1)^d$ when represented as a sum of constant-powers of univariate polynomials. We define a natural measure for the model, the support-union, and conjecture that it is $\Omega(d)$ for $f_d$.

We show a stunning connection of the conjecture to the two main problems in algebraic ... 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 >>>

TR19-008 | 20th January 2019
Ashish Dwivedi, Rajat Mittal, Nitin Saxena

Efficiently factoring polynomials modulo $p^4$

Polynomial factoring has famous practical algorithms over fields-- finite, rational \& $p$-adic. However, modulo prime powers it gets hard as there is non-unique factorization and a combinatorial blowup ensues. For example, $x^2+p \bmod p^2$ is irreducible, but $x^2+px \bmod p^2$ has exponentially many factors! We present the first randomized poly($\deg ... more >>>

TR18-036 | 21st February 2018
Michael Forbes, Sumanta Ghosh, Nitin Saxena

Towards blackbox identity testing of log-variate circuits

Derandomization of blackbox identity testing reduces to extremely special circuit models. After a line of work, it is known that focusing on circuits with constant-depth and constantly many variables is enough (Agrawal,Ghosh,Saxena, STOC'18) to get to general hitting-sets and circuit lower bounds. This inspires us to study circuits with few ... more >>>

TR18-035 | 21st February 2018
Manindra Agrawal, Sumanta Ghosh, Nitin Saxena

Bootstrapping variables in algebraic circuits

We show that for the blackbox polynomial identity testing (PIT) problem it suffices to study circuits that depend only on the first extremely few variables. One only need to consider size-$s$ degree-$s$ circuits that depend on the first $\log^{\circ c} s$ variables (where $c$ is a constant and we are ... more >>>

TR18-019 | 28th January 2018
Zeyu Guo, Nitin Saxena, Amit Sinhababu

Algebraic dependencies and PSPACE algorithms in approximative complexity

Revisions: 1

Testing whether a set $\mathbf{f}$ of polynomials has an algebraic dependence is a basic problem with several applications. The polynomials are given as algebraic circuits. Algebraic independence testing question is wide open over finite fields (Dvir, Gabizon, Wigderson, FOCS'07). The best complexity known is NP$^{\#\rm P}$ (Mittmann, Saxena, Scheiblechner, Trans.AMS'14). ... more >>>

TR17-153 | 9th October 2017
Pranjal Dutta, Nitin Saxena, Amit Sinhababu

Discovering the roots: Uniform closure results for algebraic classes under factoring

Newton iteration (NI) is an almost 350 years old recursive formula that approximates a simple root of a polynomial quite rapidly. We generalize it to a matrix recurrence (allRootsNI) that approximates all the roots simultaneously. In this form, the process yields a better circuit complexity in the case when the ... more >>>

TR17-035 | 23rd February 2017
Manindra Agrawal, Michael Forbes, Sumanta Ghosh, Nitin Saxena

Small hitting-sets for tiny arithmetic circuits or: How to turn bad designs into good

Research in the last decade has shown that to prove lower bounds or to derandomize polynomial identity testing (PIT) for general arithmetic circuits it suffices to solve these questions for restricted circuits. In this work, we study the smallest possibly restricted class of circuits, in particular depth-$4$ circuits, which would ... 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 >>>

TR16-009 | 28th January 2016
Rohit Gurjar, Arpita Korwar, Nitin Saxena

Identity Testing for constant-width, and commutative, read-once oblivious ABPs

We give improved hitting-sets for two special cases of Read-once Oblivious Arithmetic Branching Programs (ROABP). First is the case of an ROABP with known variable order. The best hitting-set known for this case had cost $(nw)^{O(\log n)}$, where $n$ is the number of variables and $w$ is the width of ... more >>>

TR14-158 | 26th November 2014
Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf

Deterministic Identity Testing for Sum of Read Once ABPs

Revisions: 2

A read once ABP is an arithmetic branching program with each variable occurring in at most one layer. We give the first polynomial time whitebox identity test for a polynomial computed by a sum of constantly many ROABPs. We also give a corresponding blackbox algorithm with quasi-polynomial time complexity, i.e. ... more >>>

TR14-085 | 29th June 2014
Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena

Hitting-sets for ROABP and Sum of Set-Multilinear circuits

We give a $n^{O(\log n)}$-time ($n$ is the input size) blackbox polynomial identity testing algorithm for unknown-order read-once oblivious algebraic branching programs (ROABP). The best time-complexity known for this class was $n^{O(\log^2 n)}$ due to Forbes-Saptharishi-Shpilka (STOC 2014), and that too only for multilinear ROABP. We get rid of their ... more >>>

TR13-186 | 27th December 2013
Nitin Saxena

Progress on Polynomial Identity Testing - II

We survey the area of algebraic complexity theory; with the focus being on the problem of polynomial identity testing (PIT). We discuss the key ideas that have gone into the results of the last few years.

more >>>

TR13-174 | 6th December 2013
Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena

Hitting-sets for low-distance multilinear depth-$3$

The depth-$3$ model has recently gained much importance, as it has become a stepping-stone to understanding general arithmetic circuits. Its restriction to multilinearity has known exponential lower bounds but no nontrivial blackbox identity tests. In this paper we take a step towards designing such hitting-sets. We define a notion of ... more >>>

TR12-113 | 7th September 2012
Manindra Agrawal, Chandan Saha, Nitin Saxena

Quasi-polynomial Hitting-set for Set-depth-$\Delta$ Formulas

We call a depth-$4$ formula $C$ $\textit{ set-depth-4}$ if there exists a (unknown) partition $X_1\sqcup\cdots\sqcup X_d$ of the variable indices $[n]$ that the top product layer respects, i.e. $C(\mathbf{x})=\sum_{i=1}^k {\prod_{j=1}^{d} {f_{i,j}(\mathbf{x}_{X_j})}}$ $ ,$ where $f_{i,j}$ is a $\textit{sparse}$ polynomial in $\mathbb{F}[\mathbf{x}_{X_j}]$. Extending this definition to any depth - we call ... more >>>

TR12-068 | 25th May 2012
Manuel Arora, Gábor Ivanyos, Marek Karpinski, Nitin Saxena

Deterministic Polynomial Factoring and Association Schemes

The problem of finding a nontrivial factor of a polynomial $f(x)$ over a finite field $\mathbb{F}_q$ has many known efficient, but randomized, algorithms. The deterministic complexity of this problem is a famous open question even assuming the generalized Riemann hypothesis (GRH). In this work we improve the state of the ... more >>>

TR12-014 | 20th February 2012
Johannes Mittmann, Nitin Saxena, Peter Scheiblechner

Algebraic Independence in Positive Characteristic -- A p-Adic Calculus

A set of multivariate polynomials, over a field of zero or large characteristic, can be tested for algebraic independence by the well-known Jacobian criterion. For fields of other characteristic $p>0$, there is no analogous characterization known. In this paper we give the first such criterion. Essentially, it boils down to ... more >>>

TR11-143 | 2nd November 2011
Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, Nitin Saxena

Jacobian hits circuits: Hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits

We present a single, common tool to strictly subsume all known cases of polynomial time blackbox polynomial identity testing (PIT) that have been hitherto solved using diverse tools and techniques. In particular, we show that polynomial time hitting-set generators for identity testing of the two seemingly different and well studied ... more >>>

TR11-022 | 14th February 2011
Malte Beecken, Johannes Mittmann, Nitin Saxena

Algebraic Independence and Blackbox Identity Testing

Algebraic independence is an advanced notion in commutative algebra that generalizes independence of linear polynomials to higher degree. Polynomials $\{f_1,\ldots, f_m\} \subset \mathbb{F}[x_1,\ldots, x_n]$ are called algebraically independent if there is no non-zero polynomial $F$ such that $F(f_1, \ldots, f_m) = 0$. The transcendence degree, $\mbox{trdeg}\{f_1,\ldots, f_m\}$, is the maximal ... more >>>

TR11-021 | 13th February 2011
Chandan Saha, Ramprasad Saptharishi, Nitin Saxena

A Case of Depth-3 Identity Testing, Sparse Factorization and Duality

Finding an efficient solution to the general problem of polynomial identity testing (PIT) is a challenging task. In this work, we study the complexity of two special but natural cases of identity testing - first is a case of depth-$3$ PIT, the other of depth-$4$ PIT.

Our first problem is ... more >>>

TR10-167 | 5th November 2010
Nitin Saxena, C. Seshadhri

Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter

Let C be a depth-3 circuit with n variables, degree d and top fanin k (called sps(k,d,n) circuits) over base field F.
It is a major open problem to design a deterministic polynomial time blackbox algorithm
that tests if C is identically zero.
Klivans & Spielman (STOC 2001) observed ... more >>>

TR10-013 | 31st January 2010
Nitin Saxena, C. Seshadhri

From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-box Identity Test for Depth-3 Circuits

Revisions: 1

We study the problem of identity testing for depth-3 circuits, over the
field of reals, of top fanin k and degree d (called sps(k,d)
identities). We give a new structure theorem for such identities and improve
the known deterministic d^{k^k}-time black-box identity test (Kayal &
Saraf, FOCS 2009) to one ... more >>>

TR09-101 | 20th October 2009
Nitin Saxena

Progress on Polynomial Identity Testing

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

TR09-058 | 4th July 2009
Gábor Ivanyos, Marek Karpinski, Nitin Saxena

Deterministic Polynomial Time Algorithms for Matrix Completion Problems

We present new deterministic algorithms for several cases of the maximum rank matrix completion
problem (for short matrix completion), i.e. the problem of assigning values to the variables in
a given symbolic matrix as to maximize the resulting matrix rank. Matrix completion belongs to
the fundamental problems in computational complexity ... more >>>

TR09-036 | 14th April 2009
Chandan Saha, Ramprasad Saptharishi, Nitin Saxena

The Power of Depth 2 Circuits over Algebras

We study the problem of polynomial identity testing (PIT) for depth
2 arithmetic circuits over matrix algebra. We show that identity
testing of depth 3 (Sigma-Pi-Sigma) arithmetic circuits over a field
F is polynomial time equivalent to identity testing of depth 2
(Pi-Sigma) arithmetic circuits over U_2(F), the ... more >>>

TR08-108 | 19th November 2008
Nitin Saxena, C. Seshadhri

An Almost Optimal Rank Bound for Depth-3 Identities

We show that the rank of a depth-3 circuit (over any field) that is simple,
minimal and zero is at most O(k^3\log d). The previous best rank bound known was
2^{O(k^2)}(\log d)^{k-2} by Dvir and Shpilka (STOC 2005).
This almost resolves the rank question first posed by ... more >>>

TR08-099 | 19th November 2008
Gábor Ivanyos, Marek Karpinski, Lajos Rónyai, Nitin Saxena

Trading GRH for algebra: algorithms for factoring polynomials and related structures

In this paper we develop techniques that eliminate the need of the Generalized
Riemann Hypothesis (GRH) from various (almost all) known results about deterministic
polynomial factoring over finite fields. Our main result shows that given a
polynomial f(x) of degree n over a finite field k, we ... 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 >>>

TR07-124 | 23rd November 2007
Nitin Saxena

Diagonal Circuit Identity Testing and Lower Bounds

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

TR05-150 | 5th December 2005
Neeraj Kayal, Nitin Saxena

Polynomial Identity Testing for Depth 3 Circuits

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

TR04-109 | 15th November 2004
Neeraj Kayal, Nitin Saxena

On the Ring Isomorphism & Automorphism Problems

We study the complexity of the isomorphism and automorphism problems for finite rings with unity.

We show that both integer factorization and graph isomorphism reduce to the problem of counting
automorphisms of rings. The problem is shown to be in the complexity class $\AM \cap co\AM$
and hence ... more >>>

ISSN 1433-8092 | Imprint