31 citations · 82 across the 22 of their papers we have counts for
23 papers · 1 filter
Deterministic identity testing paradigms for bounded top-fanin depth-4 circuits
Pranjal Dutta, Prateek Dwivedi, Nitin Saxena
Polynomial Identity Testing (PIT) is a fundamental computational problem. The famous depth- reduction result by Agrawal and Vinay (FOCS 2008) has made PIT for depth- circuits…
Special-case Algorithms for Blackbox Radical Membership, Nullstellensatz and Transcendence Degree
Abhibhav Garg, Nitin Saxena
Radical membership testing, and the special case of Hilbert's Nullstellensatz (HN), is a fundamental computational algebra problem. It is NP-hard; and has a famous PSPACE algorithm…
Efficiently factoring polynomials modulo
Ashish Dwivedi, Rajat Mittal, Nitin Saxena
Polynomial factoring has famous practical algorithms over fields-- finite, rational \& -adic. However, modulo prime powers it gets hard as there is non-unique factorization and…
Algebraic dependencies and PSPACE algorithms in approximative complexity
Zeyu Guo, Nitin Saxena, Amit Sinhababu
Testing whether a set of polynomials has an algebraic dependence is a basic problem with several applications. The polynomials are given as algebraic circuits. Algebra…
Discovering the roots: Uniform closure results for algebraic classes under factoring
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 (allRootsN…
Small hitting-sets for tiny arithmetic circuits or: How to turn bad designs into good
Manindra Agrawal, Michael Forbes, Sumanta Ghosh +1
We show that if we can design poly()-time hitting-sets for circuits of size , where is arbitrarily small and the number of variables, or ar…
Irreducibility and r-th root finding over finite fields
Vishwas Bhargava, Gábor Ivanyos, Rajat Mittal +1
Constructing -th nonresidue over a finite field is a fundamental computational problem. A related problem is to construct an irreducible polynomial of degree (where is…
Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs
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 order of the variables. T…
Deterministic Identity Testing for Sum of Read-Once Oblivious Arithmetic Branching Programs
Rohit Gurjar, Arpita Korwar, Nitin Saxena +1
A read-once oblivious arithmetic branching program (ROABP) is an arithmetic branching program (ABP) where each variable occurs in at most one layer. We give the first polynomial ti…
Hitting-sets for ROABP and Sum of Set-Multilinear circuits
Manindra Agrawal, Rohit Gurjar, Arpita Korwar +1
We give a -time ( is the input size) blackbox polynomial identity testing algorithm for unknown-order read-once oblivious algebraic branching programs (ROABP). Th…
Progress on Polynomial Identity Testing - II
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 result…
Hitting-sets for low-distance multilinear depth-3
Manindra Agrawal, Rohit Gurjar, Arpita Korwar +1
The depth- model has recently gained much importance, as it has become a stepping-stone to understanding general arithmetic circuits. Its restriction to multilinearity has known…
Quasi-polynomial Hitting-set for Set-depth-Delta Formulas
Manindra Agrawal, Chandan Saha, Nitin Saxena
We call a depth-4 formula C set-depth-4 if there exists a (unknown) partition (X_1,...,X_d) of the variable indices [n] that the top product layer respects, i.e. C(x) = \sum_{i=1}^…
Deterministic Polynomial Factoring and Association Schemes
Manuel Arora, Gábor Ivanyos, Marek Karpinski +1
The problem of finding a nontrivial factor of a polynomial f(x) over a finite field F_q has many known efficient, but randomized, algorithms. The deterministic complexity of this p…
Algebraic Independence in Positive Characteristic -- A p-Adic Calculus
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…
Jacobian hits circuits: Hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits
Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi +1
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 tool…
Algebraic Independence and Blackbox Identity Testing
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, ..., f_m} \subset \F[x_1…
Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter
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 polynomia…
From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-box Identity Test for Depth-3 Circuits
Nitin Saxena, C. Seshadhri
We study the problem of identity testing for depth-3 circuits of top fanin k and degree d. We give a new structure theorem for such identities. A direct application of our theorem…
The Power of Depth 2 Circuits over Algebras
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…
An Almost Optimal Rank Bound for Depth-3 Identities
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 k^3\log d. The previous best rank bound known was 2^{O(k^2)}(\log d)^{k-2} b…
Trading GRH for algebra: algorithms for factoring polynomials and related structures
Gábor Ivanyos, Marek Karpinski, Lajos Rónyai +1
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 facto…
Schemes for Deterministic Polynomial Factoring
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 conditiona…