All reports by Author Nitin Saxena:

__
TR20-092
| 16th June 2020
__

Ashish Dwivedi, Nitin Saxena#### Computing Igusa's local zeta function of univariates in deterministic polynomial-time

__
TR20-042
| 31st March 2020
__

Pranav Bisht, Nitin Saxena#### Poly-time blackbox identity testing for sum of log-variate constant-width ROABPs

__
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

__
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

__
TR19-008
| 20th January 2019
__

Ashish Dwivedi, Rajat Mittal, Nitin Saxena#### Efficiently factoring polynomials modulo $p^4$

__
TR18-036
| 21st February 2018
__

Michael Forbes, Sumanta Ghosh, Nitin Saxena#### Towards blackbox identity testing of log-variate circuits

__
TR18-035
| 21st February 2018
__

Manindra Agrawal, Sumanta Ghosh, Nitin Saxena#### Bootstrapping variables in algebraic circuits

__
TR18-019
| 28th January 2018
__

Zeyu Guo, Nitin Saxena, Amit Sinhababu#### Algebraic dependencies and PSPACE algorithms in approximative complexity

Revisions: 1

__
TR17-153
| 9th October 2017
__

Pranjal Dutta, Nitin Saxena, Amit Sinhababu#### Discovering the roots: Uniform closure results for algebraic classes under factoring

__
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

__
TR17-016
| 31st January 2017
__

Vishwas Bhargava, Gábor Ivanyos, Rajat Mittal, Nitin Saxena#### Irreducibility and deterministic r-th root finding over finite fields

__
TR16-009
| 28th January 2016
__

Rohit Gurjar, Arpita Korwar, Nitin Saxena#### Identity Testing for constant-width, and commutative, read-once oblivious ABPs

__
TR14-158
| 26th November 2014
__

Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf#### Deterministic Identity Testing for Sum of Read Once ABPs

Revisions: 2

__
TR14-085
| 29th June 2014
__

Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena#### Hitting-sets for ROABP and Sum of Set-Multilinear circuits

__
TR13-186
| 27th December 2013
__

Nitin Saxena#### Progress on Polynomial Identity Testing - II

__
TR13-174
| 6th December 2013
__

Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena#### Hitting-sets for low-distance multilinear depth-$3$

__
TR12-113
| 7th September 2012
__

Manindra Agrawal, Chandan Saha, Nitin Saxena#### Quasi-polynomial Hitting-set for Set-depth-$\Delta$ Formulas

__
TR12-068
| 25th May 2012
__

Manuel Arora, Gábor Ivanyos, Marek Karpinski, Nitin Saxena#### Deterministic Polynomial Factoring and Association Schemes

__
TR12-014
| 20th February 2012
__

Johannes Mittmann, Nitin Saxena, Peter Scheiblechner#### Algebraic Independence in Positive Characteristic -- A p-Adic Calculus

__
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

__
TR11-022
| 14th February 2011
__

Malte Beecken, Johannes Mittmann, Nitin Saxena#### Algebraic Independence and Blackbox Identity Testing

__
TR11-021
| 13th February 2011
__

Chandan Saha, Ramprasad Saptharishi, Nitin Saxena#### A Case of Depth-3 Identity Testing, Sparse Factorization and Duality

__
TR10-167
| 5th November 2010
__

Nitin Saxena, C. Seshadhri#### Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter

__
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

__
TR09-101
| 20th October 2009
__

Nitin Saxena#### Progress on Polynomial Identity Testing

__
TR09-058
| 4th July 2009
__

Gábor Ivanyos, Marek Karpinski, Nitin Saxena#### Deterministic Polynomial Time Algorithms for Matrix Completion Problems

__
TR09-036
| 14th April 2009
__

Chandan Saha, Ramprasad Saptharishi, Nitin Saxena#### The Power of Depth 2 Circuits over Algebras

__
TR08-108
| 19th November 2008
__

Nitin Saxena, C. Seshadhri#### An Almost Optimal Rank Bound for Depth-3 Identities

__
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

__
TR08-043
| 12th April 2008
__

Gábor Ivanyos, Marek Karpinski, Nitin Saxena#### Schemes for Deterministic Polynomial Factoring

__
TR07-124
| 23rd November 2007
__

Nitin Saxena#### Diagonal Circuit Identity Testing and Lower Bounds

__
TR05-150
| 5th December 2005
__

Neeraj Kayal, Nitin Saxena#### Polynomial Identity Testing for Depth 3 Circuits

__
TR04-109
| 15th November 2004
__

Neeraj Kayal, Nitin Saxena#### On the Ring Isomorphism & Automorphism Problems

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

Pranav Bisht, Nitin Saxena

Blackbox polynomial identity testing (PIT) affords 'extreme variable-bootstrapping' (Agrawal et al, STOC'18; PNAS'19; Guo et al, FOCS'19). This motivates us to study log-variate read-once oblivious algebraic branching programs (ROABP). We restrict width of ROABP to a constant and study the more general sum-of-ROABPs model. We give the first poly($s$)-time blackbox ... more >>>

Pranjal Dutta, Nitin Saxena, Thomas Thierauf

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

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, Rajat Mittal, Nitin Saxena

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

Michael Forbes, Sumanta Ghosh, Nitin Saxena

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

Manindra Agrawal, Sumanta Ghosh, Nitin Saxena

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

Zeyu Guo, Nitin Saxena, Amit Sinhababu

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

Pranjal Dutta, Nitin Saxena, Amit Sinhababu

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

Manindra Agrawal, Michael Forbes, Sumanta Ghosh, Nitin Saxena

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

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

Rohit Gurjar, Arpita Korwar, Nitin Saxena

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

Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf

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

Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena

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

Nitin Saxena

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 >>>Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena

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

Manindra Agrawal, Chandan Saha, Nitin Saxena

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

Manuel Arora, Gábor Ivanyos, Marek Karpinski, Nitin Saxena

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

Johannes Mittmann, Nitin Saxena, Peter Scheiblechner

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

Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, Nitin Saxena

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

Malte Beecken, Johannes Mittmann, Nitin Saxena

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

Chandan Saha, Ramprasad Saptharishi, Nitin Saxena

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

Nitin Saxena, C. Seshadhri

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

Nitin Saxena, C. Seshadhri

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

Nitin Saxena

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

Gábor Ivanyos, Marek Karpinski, Nitin Saxena

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

Chandan Saha, Ramprasad Saptharishi, Nitin Saxena

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

Nitin Saxena, C. Seshadhri

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

Gábor Ivanyos, Marek Karpinski, Lajos Rónyai, Nitin Saxena

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

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

Nitin Saxena

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

Neeraj Kayal, Nitin Saxena

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

Neeraj Kayal, Nitin Saxena

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