A central question in mathematics and computer science is the question of determining whether a given ideal $I$ is prime, which geometrically corresponds to the zero set of $I$, denoted $Z(I)$, being irreducible. The case of principal ideals (i.e., $m=1$) corresponds to the more familiar absolute irreducibility testing of polynomials, where the seminal work of (Kaltofen 1995) yields a randomized, polynomial time algorithm for this problem. However, when $m > 1$, the complexity of the primality testing problem seems much harder. The current best algorithms for this problem are only known to be in EXPSPACE. In this work, we significantly reduce the complexity-theoretic gap for the ideal primality testing problem for the important families of ideals $I$ (namely, radical ideals and equidimensional Cohen-Macaulay ideals). For these classes of ideals, assuming the Generalized Riemann Hypothesis, we show that primality testing lies in $\Sigma_3^p \cap \Pi_3^p$. This significantly improves the upper bound for these classes, approaching their lower bound, as the primality testing problem is coNP-hard for these classes of ideals. Another consequence of our results is that for equidimensional Cohen-Macaulay ideals, we get the first PSPACE algorithm for primality testing, exponentially improving the space and time complexity of prior known algorithms.

The border, or the approximative, model of algebraic computation (VP) is quite popular due to the Geometric Complexity Theory (GCT) approach to P≠NP conjecture, and its complex analytic origins. On the flip side, the definition of the border is inherently existential in the field constants that the model employs. In particular, a poly-size border circuit C(ε, x) cannot be compactly presented in reality, as the limit parameter ε may require exponential precision. In this work we resolve this issue by giving a constructive, or a presentable, version of border circuits and state its applications. We make border presentable by restricting the circuit C to use only those constants, in the function field Fq(ε), that it can generate by the ring operations on {ε}∪Fq, and their division, within poly-size circuit. This model is more expressive than VP as it affords exponential-degree in ε; and analogous to the usual border, we define new border classes called VPε and VNPε. We prove that both these (now called presentable border) classes lie in VNP. Such a ’debordering’ result is not known for the classical border classes VP and respectively for VNP. We pose VPε=VP as a new conjecture to study the border. The heart of our technique is a newly formulated exponential interpolation over a finite field, to bound the Boolean complexity of the coefficients before deducing the algebraic complexity. It attacks two factorization problems which were open before. We make progress on (Conj.8.3 in Bürgisser 2000, FOCS 2001) and solve (Conj.2.1 in Bürgisser 2000; Chou,Kumar,Solomon CCC 2018) over all finite fields: 1. Each poly-degree irreducible factor, with multiplicity coprime to field characteristic, of a poly-size circuit (of possibly exponential-degree), is in VNP. 2. For all finite fields, and all factors, VNP is closed under factoring. Consequently, factors of VP are always in VNP. The prime characteristic cases were open before due to the inseparability obstruction (i.e. ‍when the multiplicity is not coprime to q).

Abstract For a polynomial f, a weighted sum-of-squares representation (SOS) has the form $$f = \sum_{i\in [s]} c_i f_i^2$$ f = ∑ i ∈ [ s ] c i f i 2 , where the weights $$c_i$$ c i are field elements. The size of the representation is the number of monomials that appear across the $$f_i$$ f i 's. Its minimum across all such decompositions is called the support-sum S(f) of f. For a univariate polynomial f of degree d of full support, a lower bound for the support-sum is $$S(f) \ge \sqrt d$$ S ( f ) ≥ d . We show that the existence of an explicit univariate polynomial f with support-sum just slightly larger than the lower bound, that is, $$S(f) \ge d^{0.5+\varepsilon}$$ S ( f ) ≥ d 0.5 + ε , for some $$\varepsilon > 0$$ ε > 0 , implies that $$\ne$$ ≠ , the major open problem in algebraic complexity. In fact, our proof works for some subconstant functions $$\varepsilon(d) > 0$$ ε ( d ) > 0 as well. We also consider the sum-of-cubes representation (SOC) of polynomials. We show that an explicit hard polynomial implies both blackbox-PIT is in , and $$\neq$$ ≠ .

Finding roots of a bivariate polynomial f(x1, x2), over a prime field , is a fundamental question with a long history and several practical algorithms are now known. Effective algorithms for describing the roots modulo pk, k ≥ 2, for any general bivariate polynomial, were unknown until the present paper. The main obstruction is lifting the singular roots to . Such roots may be numerous and behave unpredictably, i.e., they may or may not lift from to .

Mulmuley and Sohoni (2001) proposed an ambitious program, the Geometric Complexity Theory (GCT), to prove $P\neq NP$ and related conjectures using algebraic geometry and representation theory. Gradually, GCT has introduced new structures and questions in complexity. GCT tries to capture the algebraic/geometric notion of ’approximation’ by defining border classes. Surprisingly, (Kumar ToCT’20) proved the universal power of the border of top-fanin- 2 depth-3 circuits $(\overline{\Sigma^{[2]}\Pi\Sigma})$; which is in complete contrast to its classical model. Recently, (Dutta,Dwivedi,Saxena, FOCS’21) put an upper bound, by showing that bounded-top-fanin border depth-3 circuits $(\overline{\Sigma^{[k]}\Pi\Sigma}$ for constant $k)$ can be computed by a polynomial-size algebraic branching program (ABP). It was left open to show an exponential separation between the class of ABPs and $\overline{\Sigma^{[k]}\Pi\Sigma}$. In this article, we show a strongly-exponential separation between any two consecutive border classes, $\overline{\Sigma^{[k]}\Pi\Sigma}$ and $\Sigma^{[k+1]}\Pi\Sigma$, establishing an optimal hierarchy of constant topfanin border depth- 3 circuits. Put in GCT language: we prove an exponential-hierarchy for padded- k-th-secant-varieties of the Chow variety of $\mathbb{F}^{n+1} $. This positively answers [Open question 2 of Dutta,Dwivedi,Saxena FOCS’21] and [Problem 8.10 with constant r, of Landsberg, Annal.Ferrara’15]. Full version: https://www.cse.iitk.ac.in/users/nitin/papers/exphierarchy.pdf

Newton iteration is an almost 350-year-old recursive formula that approximates a simple root of a polynomial quite rapidly. We generalize it to a matrix recurrence (allRootsNI) that approximates all roots simultaneously. In this form, the process yields better circuit complexity in the case when the number of rootsris small but the multiplicities are exponentially large. Our method sets up a linear system inrunknowns and iteratively builds the roots as formal power series. For an algebraic circuit \( f(x_1,\ldots ,x_n) \) of sizes, we prove that each factor has size at most a polynomial insand the degree of the squarefree part off. Consequently, if \( f_1 \) is a \( 2^{\Omega (n)} \) -hard polynomial, then any nonzero multiple \( \prod _{i} f_i^{e_i} \) is equally hard for arbitrary positive \( e_i \) ’s, assuming that \( \sum _i\deg (f_i) \) is at most \( 2^{O(n)} \) . It is an old open question whether the class of poly(n) size formulas (respectively, algebraic branching programs) is closed under factoring. We show that given a polynomialfof degree \( n^{O(1)} \) and formula (respectively, algebraic branching program) size \( n^{O(\log n)} \) , we can find a similar-size formula (respectively, algebraic branching program) factor in randomized poly( \( n^{\log n} \) ) time. Consequently, if the determinant requires an \( n^{\Omega (\log n)} \) size formula, then the same can be said about any of its nonzero multiples. In all of our proofs, we exploit the following property of multivariate polynomial factorization. Under a random linear transformation \( \tau \) , the polynomial \( f(\tau \overline{x}) \) completely factors via power series roots. Moreover, the factorization adapts well to circuit complexity analysis. Therefore, with the help of the strong mathematical characterizations and the ‘allRootsNI’ technique, we make significant progress towards the old open problems; supplementing the vast body of classical results and concepts in algebraic circuit factorization (e.g., [ 17 , 51 , 54 , 111 ]).

Polynomial Identity Testing (PIT) is a fundamental computational problem. The famous depth-4 reduction (Agrawal & Vinay, FOCS'08) has made PIT for depth-4 circuits, an enticing pursuit. The largely open special-cases of sum-product-of-sum-of-univariates (Σ^[k] Π Σ ∧) and sum-product-of-constant-degree-polynomials (Σ^[k] Π Σ Π^[δ]), for constants k, δ, have been a source of many great ideas in the last two decades. For eg. depth-3 ideas (Dvir & Shpilka, STOC'05; Kayal & Saxena, CCC'06; Saxena & Seshadhri, FOCS'10, STOC'11); depth-4 ideas (Beecken, Mittmann & Saxena, ICALP'11; Saha,Saxena & Saptharishi, Comput.Compl.'13; Forbes, FOCS'15; Kumar & Saraf, CCC'16); geometric Sylvester-Gallai ideas (Kayal & Saraf, FOCS'09; Shpilka, STOC'19; Peleg & Shpilka, CCC'20, STOC'21). We solve two of the basic underlying open problems in this work. We give the first polynomial-time PIT for Σ^[k] Π Σ ∧. Further, we give the first quasipolynomial time blackbox PIT for both Σ^[k] Π Σ ∧ and Σ^[k] Π Σ Π^[δ]. No subexponential time algorithm was known prior to this work (even if k = δ = 3). A key technical ingredient in all the three algorithms is how the logarithmic derivative, and its power-series, modify the top Π-gate to ∧.

Border complexity of polynomials plays an integral role in GCT (Geometric Complexity Theory) approach to P versus NP. It tries to formalize the notion of ‘approximating a polynomial’ via limits (Bürgisser FOCS'01). This raises the open question whether border of VP is same as VP or not; as the approximation involves exponential precision, which may not be efficiently simulable. Recently (Kumar ToCT'20) proved the universal power of the border of top-fanin-2 depth-3 circuits. Here we answer some of the related open questions. We show that the border of bounded top-fanin-k depth-3 circuits, for constant k, is relatively easy- it can be computed by a polynomial size algebraic branching program (ABP). There were hardly any de-bordering results known for prominent models before our result. Moreover, we give the first quasipolynomial-time black-box identity test for the same. Prior best was in PSPACE (Forbes,Shpilka STOC'18). Also, with more technical work, we extend our results to depth-4. Our de-bordering paradigm is a multi-step process; in short we call it DiDIL -divide, derive, induct, with limit. It ‘almost’ reduces border top-fanin-k depth-3 circuits to special cases of read-once oblivious algebraic branching programs (ROABPs) in any-order. Full version: https://www.cse.iitk.ac.in/users/nitin/papers/border-depth3.pdf

For a polynomial f, we study the sum of squares representation (SOS), i.e. f = ∑_{i ∈ [s]} c_i f_i² , where c_i are field elements and the f_i’s are polynomials. The size of the representation is the number of monomials that appear across the f_i’s. Its minimum is the support-sum S(f) of f. For simplicity of exposition, we consider univariate f. A trivial lower bound for the support-sum of, a full-support univariate polynomial, f of degree d is S(f) ≥ d^{0.5}. We show that the existence of an explicit polynomial f with support-sum just slightly larger than the trivial bound, that is, S(f) ≥ d^{0.5+ε(d)}, for a sub-constant function ε(d) > ω(√{log log d/log d}), implies that VP ≠ VNP. The latter is a major open problem in algebraic complexity. A further consequence is that blackbox-PIT is in SUBEXP. Note that a random polynomial fulfills the condition, as there we have S(f) = Θ(d). We also consider the sum-of-cubes representation (SOC) of polynomials. In a similar way, we show that here, an explicit hard polynomial even implies that blackbox-PIT is in P.

Polynomial factoring has famous practical algorithms over fields-- finite, rational and p-adic. However, modulo prime powers, factoring gets harder because 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 f, łog p) time algorithm to factor a given univariate integral f(x) modulo p^k, for a prime p and k łeq 4. Thus, we solve the open question of factoring modulo p^3 posed in (Sircana, ISSAC'17). Our method reduces the general problem of factoring f(x) mod p^k to that of \em root finding in a related polynomial E(y) \bmodłangle p^k, \varphi(x)^\ell \rangle for some irreducible \varphi \bmod p. We can efficiently solve the latter for kłe4, by incrementally transforming E(y). Moreover, we discover an efficient refinement of Hensel lifting to lift factors of f(x) \bmod p to those \bmod\ p^4 (if possible). This was previously unknown, as the case of repeated factors of f(x) \bmod p forbids classical Hensel lifting.

Radical membership testing, resp. its special case of Hilbert's Nullstellensatz (HN), is a fundamental computational algebra problem. It is NP-hard; and has a famous PSPACE algorithm due to effective Nullstellensatz bounds. We identify a useful case of these problems where practical algorithms, & improved bounds, could be given---When transcendence degree (tr.deg) r of the input polynomials is smaller than the number of variables n. If d is the degree bound on the input polynomials, then we solve radical membership (even if input polynomials are blackboxes) in around dr time. The prior best was > dn time (always, dn ≥ dr). Also, we significantly improve effective Nullstellensatz degree-bound, when r ≪ n.

Testing whether a set 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). Previously, the best complexity known was NP^{#P} (Mittmann, Saxena, Scheiblechner, Trans.AMS'14). In this work we put the problem in AM cap coAM. In particular, dependence testing is unlikely to be NP-hard and joins the league of problems of "intermediate" complexity, eg. graph isomorphism & integer factoring. Our proof method is algebro-geometric- estimating the size of the image/preimage of the polynomial map f over the finite field. A gap in this size is utilized in the AM protocols. Next, we study the open question of testing whether every annihilator of f has zero constant term (Kayal, CCC'09). We give a geometric characterization using Zariski closure of the image of f; introducing a new problem called approximate polynomials satisfiability (APS). We show that APS is NP-hard and, using projective algebraic-geometry ideas, we put APS in PSPACE (prior best was EXPSPACE via Gröbner basis computation). As an unexpected application of this to approximative complexity theory we get- over any field, hitting-sets for overline{VP} can be verified in PSPACE. This solves an open problem posed in (Mulmuley, FOCS'12, J.AMS 2017); greatly mitigating the GCT Chasm (exponentially in terms of space complexity).

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 variables, eg. logarithmic in the size s. We give the first poly(s)-time blackbox identity test for n=O(log s) variate size-s circuits that have poly(s)-dimensional partial derivative space; eg. depth-3 diagonal circuits (or Sigma wedge Sigma^n). The former model is well-studied (Nisan,Wigderson, FOCS'95) but no poly(s2^n)-time identity test was known before us. We introduce the concept of cone-closed basis isolation and prove its usefulness in studying log-variate circuits. It subsumes the previous notions of rank-concentration studied extensively in the context of ROABP models.

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 number of roots r is small but the multiplicities are exponentially large. Our method sets up a linear system in r unknowns and iteratively builds the roots as formal power series. For an algebraic circuit f(x1,…,xn) of size s we prove that each factor has size at most a polynomial in: s and the degree of the squarefree part of f. Consequently, if f1 is a 2Ω(n)-hard polynomial then any nonzero multiple ∏i fiei is equally hard for arbitrary positive ei’s, assuming that ∑ideg(fi) is at most 2O(n).

Constructing r-th nonresidue over a finite field is a fundamental computational problem. A related problem is to construct an irreducible polynomial of degree re (where r is a prime) over a given finite field Fq of characteristic p (equivalently, constructing the bigger field Fqre). Both these problems have famous randomized algorithms but the derandomization is an open question. We give some new connections between these two problems and their variants.

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 the ROABP. Even for a constant-width ROABP, nothing better than a quasi-polynomial bound was known. We improve the hitting-set complexity for the known-order case to n^{O(log(w))}. In particular, this gives the first polynomial time hitting-set for constant-width ROABP (known-order). However, our hitting-set works only over those fields whose characteristic is zero or large enough. To construct the hitting-set, we use the concept of the rank of partial derivative matrix. Unlike previous approaches whose starting point is a monomial map, we use a polynomial map directly. The second case we consider is that of commutative ROABP. The best known hitting-set for this case had cost d^{O(log(w))}(nw)^{O(log(log(w)))}, where d is the individual degree. We improve this hitting-set complexity to (ndw)^{O(log(log(w)))}. We get this by achieving rank concentration more efficiently.

Integer factoring is a curious number theory problem with wide applications in complexity and cryptography. The best known algorithm to factor a number n takes time, roughly, exp(2*log^{1/3}(n)*log^{2/3}(log(n))) (number field sieve, 1989). One basic idea used is to find two squares, possibly in a number field, that are congruent modulo n. Several variants of this idea have been utilized to get other factoring algorithms in the last century. In this work we intend to explore new ideas towards integer factoring. In particular, we adapt the AKS primality test (2004) ideas for integer factoring. In the motivating case of semiprimes n=pq, i.e. p

The motivation for this work comes from two problems--test algebraic independence of arithmetic circuits over a field of small characteristic, and generalize the structural property of algebraic dependence used by (Kumar, Saraf CCC'16) to arbitrary fields. It is known that in the case of zero, or large characteristic, using a classical criterion based on the Jacobian, we get a randomized poly-time algorithm to test algebraic independence. Over small characteristic, the Jacobian criterion fails and there is no subexponential time algorithm known. This problem could well be conjectured to be in RP, but the current best algorithm puts it in NP^#P (Mittmann, Saxena, Scheiblechner Trans.AMS'14). Currently, even the case of two bivariate circuits over F_2 is open. We come up with a natural generalization of Jacobian criterion, that works over all characteristic. The new criterion is efficient if the underlying inseparable degree is promised to be a constant. This is a modest step towards the open question of fast independence testing, over finite fields, posed in (Dvir, Gabizon, Wigderson FOCS'07). In a set of linearly dependent polynomials, any polynomial can be written as a linear combination of the polynomials forming a basis. The analogous property for algebraic dependence is false, but a property approximately in that spirit is named as ``functional dependence'' in (Kumar, Saraf CCC'16) and proved for zero or large characteristic. We show that functional dependence holds for arbitrary fields, thereby answering the open questions in (Kumar, Saraf CCC'16). Following them we use the functional dependence lemma to prove the first exponential lower bound for locally low algebraic rank circuits for arbitrary fields (a model that strongly generalizes homogeneous depth-4 circuits). We also recover their quasipoly-time hitting-set for such models, for fields of characteristic smaller than the ones known before. Our results show that approximate functional dependence is indeed a more fundamental concept than the Jacobian as it is field independent. We achieve the former by first picking a ``good'' transcendence basis, then translating the circuits by new variables, and finally approximating them by truncating higher degree monomials. We give a tight analysis of the ``degree'' of approximation needed in the criterion. To get the locally low algebraic rank circuit applications we follow the known shifted partial derivative based methods.

We present a single common tool to strictly subsume all known cases of polynomial time black box polynomial identity testing (PIT), that have been hitherto solved using diverse tools and techniques, over fields of zero or large characteristic. In particular, we show that polynomial (in the size of the circuit) time hitting-set generators for identity testing of the two seemingly different and well studied models---depth-3 circuits with bounded top fanin, and constant-depth constant-read multilinear formulas---can be constructed using one common algebraic-geometry theme: Jacobian captures algebraic independence. By exploiting the Jacobian, we design the first efficient hitting-set generators for broad generalizations of the above-mentioned models, namely, (a) depth-3 ($\Sigma \Pi \Sigma$) circuits with constant transcendence degree of the polynomials computed by the product gates (no bounded top fanin restriction), and (b) constant-depth constant-occur formulas (no multilinear restriction). Constant occur of a variable, as we define it, is a more general concept than constant read. Also, earlier work on the latter model assumed that the formula is multilinear. Thus, our work goes further beyond the related results obtained by Saxena and Seshadhri [STOC, ACM, New York, 2011, pp. 431--440], Saraf and Volkovich [STOC, ACM, New York, 2011, pp. 421--430], Anderson, van Melkebeek, and Volkovich, [IEEE Conference on Computational Complexity, IEEE, Piscataway, NJ, 2011, pp. 273--282], Beecken, Mittmann, and Saxena [ICALP, Springer, New York, 2011, pp. 134--148] and Grenet et al. [Proceedings of the 30th Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Schloss Dagstuhl--Liebniz--Zentrum für Informatik, Wadern, Germany, 2011, pp. 127--139] and brings them under one unifying technique. In addition, using the same Jacobian-based approach, we prove exponential lower bounds for the immanant (which includes permanent and determinant) on the same depth-3 and depth-4 models for which we give efficient PIT algorithms. Our results reinforce the intimate connection between identity testing and lower bounds by exhibiting a concrete mathematical tool---the Jacobian. The Jacobian is equally effective in solving both the problems on certain interesting and previously well-investigated (but not well understood) models of computation.

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 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 n^(O(log(n))). In both the cases, our time complexity is double exponential in the number of ROABPs. ROABPs are a generalization of set-multilinear depth-3 circuits. The prior results for the sum of constantly many set-multilinear depth-3 circuits were only slightly better than brute-force, i.e. exponential-time. Our techniques are a new interplay of three concepts for ROABP: low evaluation dimension, basis isolating weight assignment and low-support rank concentration. We relate basis isolation to rank concentration and extend it to a sum of two ROABPs using evaluation dimension (or partial derivatives).

We give an $n^{O(\log n)}$-time ($n$ is the input size) blackbox polynomial identity testing algorithm for unknown-order read-once oblivious arithmetic branching programs (ROABPs). The best time complexity known for blackbox polynomial identity testing (PIT) for this class was $n^{O(\log^2 n)}$ due to Forbes, Saptharishi, and Shpilka [Proceedings of the 2014 ACM Symposium on Theory of Computing, 2014, pp. 867--875]. Moreover, their result holds only when the individual degree is small, while we do not need any such assumption. With this, we match the time complexity for the unknown-order ROABP with the known-order ROABP (due to Forbes and Shpilka [Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 2013, pp. 243--252]) and also with the depth-3 set-multilinear circuits (due to Agrawal, Saha, and Saxena [Proceedings of the 2013 ACM Symposium on Theory of Computing, 2013, pp. 321--330]). Our proof is simpler and involves a new technique called basis isolation. The depth-3 model has recently gained much importance, as it has become a stepping stone to understanding general arithmetic circuits. Multilinear depth-3 circuits are known to have exponential lower bounds but no polynomial time blackbox identity tests. In this paper, we take a step toward designing such hitting-sets. We give the first subexponential whitebox PIT for the sum of constantly many set-multilinear depth-3 circuits. To achieve this, we define the notions of distance and base sets. Distance, for a multilinear depth-3 circuit (say, in $n$ variables and $k$ product gates), measures how far the variable partitions corresponding to the product gates are from being a mere refinement of each other. The 1-distance circuits strictly contain the set-multilinear model, while $n$-distance captures general multilinear depth-3. We design a hitting-set in time $(nk)^{O(\Delta \log n)}$ for $\Delta$-distance. Further, we give an extension of our result to models where the distance is large (close to $n$) but is small when restricted to certain base sets (of variables). We also explore a new model of ROABPs where the factor matrices are invertible (called invertible-factor ROABPs). We design a hitting-set in time poly($n^{w^2}$) for width-$w$ invertible-factor ROABPs. Further, we could do without the invertibility restriction when w=2. Previously, the best result for width-2 ROABPs was quasi-polynomial time [M. A. Forbes, R. Saptharishi, and A. Shpilka, Proceedings of the 2014 ACM Symposium on Theory of Computing, 2014, pp. 867--875].

We call a depth-4 formula C set-depth-4 if there exists a (unknown) partition X1⊔⋅⋅⋅⊔ Xd of the variable indices [n] that the top product layer respects, i.e. C(term{x})=∑i=1k ∏j=1d fi,j(term{x}Xj), where fi,j is a sparse polynomial in F[term{x}Xj]. Extending this definition to any depth - we call a depth-D formula C (consisting of alternating layers of Σ and Π gates, with a Σ-gate on top) a set-depth-D formula if every Π-layer in C respects a (unknown) partition on the variables; if D is even then the product gates of the bottom-most Π-layer are allowed to compute arbitrary monomials. In this work, we give a hitting-set generator for set-depth-D formulas (over any field) with running time polynomial in exp((D2log s) Δ - 1), where s is the size bound on the input set-depth-D formula. In other words, we give a quasi-polynomial time blackbox polynomial identity test for such constant-depth formulas. Previously, the very special case of D=3 (also known as set-multilinear depth-3 circuits) had no known sub-exponential time hitting-set generator. This was declared as an open problem by Shpilka & Yehudayoff (FnT-TCS 2010); the model being first studied by Nisan & Wigderson (FOCS 1995) and recently by Forbes & Shpilka (STOC 2012 & ECCC TR12-115). Our work settles this question, not only for depth-3 but, up to depth εlog s / log log s, for a fixed constant ε < 1. The technique is to investigate depth-D formulas via depth-(D-1) formulas over a Hadamard algebra, after applying a 'shift' on the variables. We propose a new algebraic conjecture about the low-support rank-concentration in the latter formulas, and manage to prove it in the case of set-depth-D formulas.

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 that improves the known deterministic d k O ( k ) -time blackbox identity test over rationals [Kayal and Saraf, 2009] to one that takes d O ( k 2 ) -time. Our structure theorem essentially says that the number of independent variables in a real depth-3 identity is very small. This theorem affirmatively settles the strong rank conjecture posed by Dvir and Shpilka [2006]. We devise various algebraic tools to study depth-3 identities, and use these tools to show that any depth-3 identity contains a much smaller nucleus identity that contains most of the “complexity” of the main identity. The special properties of this nucleus allow us to get near optimal rank bounds for depth-3 identities. The most important aspect of this work is relating a field-dependent quantity, the Sylvester-Gallai rank bound , to the rank of depth-3 identities. We also prove a high-dimensional Sylvester-Gallai theorem for all fields, and get a general depth-3 identity rank bound (slightly improving previous bounds).

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, over fields of zero or large characteristic. In particular, we show that polynomial time hitting-set generators for identity testing of the two seemingly different and well studied models - depth-3 circuits with bounded top fanin, and constant-depth constant-read multilinear formulas - can be constructed using one common algebraic-geometry theme: Jacobian captures algebraic independence. By exploiting the Jacobian, we design the first efficient hitting-set generators for broad generalizations of the above-mentioned models, namely: - depth-3 (Ω Π Ω) circuits with constant transcendence degree of the polynomials computed by the product gates (no bounded top fanin restriction), and - constant-depth constant-occur formulas (no multilinear restriction). Constant-occur of a variable, as we define it, is a much more general concept than constant-read. Also, earlier work on the latter model assumed that the formula is multilinear. Thus, our work goes further beyond the related results obtained by Saxena & Seshadhri (STOC 2011), Saraf & Volkovich (STOC 2011), Anderson et al. (CCC 2011), Beecken et al. (ICALP 2011) and Grenet et al. (FSTTCS 2011), and brings them under one unifying technique.

Let $C$ be a depth-3 circuit with $n$ variables, degree $d$, and top-fanin $k$ (called ${\Sigma\Pi\Sigma}(k,d,n)$ circuits) over base field ${\mathbb{F}}$. It is a major open problem to design a deterministic polynomial time blackbox algorithm that tests whether $C$ is identically zero. Klivans and Spielman [Proceedings of the 33rd Annual Symposium on Theory of Computing (STOC), 2001, pp. 216--223] observed that the problem is open even when $k$ is a constant. This case has been subjected to serious scrutiny over the past few years, starting from the work of Dvir and Shpilka [SIAM J. Comput., 36 (2007), pp. 1404--1434]. We give the first polynomial time blackbox algorithm for this problem. Our algorithm runs in time ${\mbox{\rm poly}}(n)d^k$, regardless of the base field. The only field for which polynomial time algorithms were previously known is ${\mathbb{F}} = {\mathbb{Q}}$ [N. Kayal and S. Saraf, Proceedings of the 50th Annual Symposium on Foundations of Computer Science (FOCS), 2009, pp. 198--207; N. Saxena and C. Seshadhri, Proceedings of the 51st Annual Symposium on Foundations of Computer Science (FOCS), 2010, pp. 21--29]. This is the first blackbox algorithm for depth-3 circuits that does not use the rank-based approaches of Karnin and Shpilka [Proceedings of the 24th Annual Conference on Computational Complexity (CCC), 2009, pp. 274--285]. We prove an important tool for the study of depth-3 identities. We design a blackbox polynomial time transformation that reduces the number of variables in a ${\Sigma\Pi\Sigma}(k,d,n)$ circuit to $k$ variables but preserves the identity structure.

Let C be a depth-3 circuit with n variables, degree d and top fanin k (called ΣΠΣ(k,d,n) circuits) over base field FF. 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 that the problem is open even when k is a constant. This case has been subjected to a serious study over the past few years, starting from the work of Dvir & Shpilka (STOC 2005).

We study the problem of polynomial identity testing for depth-3 circuits of degree d and top fanin k. The rank of any such identity is essentially the minimum number of independent variables present. Small bounds on this quantity imply fast deterministic identity testers for these circuits. Dvir and Shpilka [SIAM J. Comput., 36 (2007), pp. 1404–1434] initiated the study of the rank and showed that any depth-3 identity (barring some uninteresting corner cases) has a rank of $2^{O(k^2)}(\log d)^{k-2}$. We show that the rank of a depth-3 identity is at most $O(k^3\log d)$. This bound is almost tight, since we also provide an identity of rank $\Omega(k\log d)$. Our rank bound significantly improves (dependence on k exponentially reduced) the best known deterministic black-box identity tests for depth-3 circuits by Karnin and Shpilka [Z. Karnin and A. Shpilka, in Proceedings of the 23rd CCC, 2008, pp. 280–291]. Our techniques also shed light on the factorization pattern of nonzero depth-3 circuits: the rank of linear factors of a simple, minimal, and nonzero depth-3 circuit (over any field) is at most $O(k^3\log d)$. The novel feature of this work is a new notion of maps between sets of linear forms, called ideal matchings, used to study depth-3 circuits. We prove interesting structural results about depth-3 identities using these techniques. We believe that these ideas may lead to the goal of a deterministic polynomial time identity test for these circuits.

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 improves the known deterministic d -time black-box identity test over rationals (Kayal & Saraf, FOCS 2009) to one that takes d(O(k2))-time. Our structure theorem essentially says that the number of independent variables in a real depth-3 identity is very small. This theorem affirmatively settles the strong rank conjecture posed by Dvir & Shpilka (STOC 2005). We devise a powerful algebraic framework and develop tools to study depth-3 identities. We use these tools to show that any depth-3 identity contains a much smaller nucleus identity that contains most of the "complexity" of the main identity. The special properties of this nucleus allow us to get almost optimal rank bounds for depth-3 identities.

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 to maximize the resulting matrix rank. Matrix completion is one of the fundamental problems in computational complexity. It has numerous important algorithmic applications, among others, in computing dynamic transitive closures or multicast network codings [N. J. A. Harvey, D. R. Karger, and K. Murota, Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005, pp. 489–498; N. J. A. Harvey, D. R. Karger, and S. Yekhanin, Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006, pp. 1103–1111]. We design efficient deterministic algorithms for common generalizations of the results of Lovász and Geelen on this problem by allowing linear polynomials in the entries of the input matrix such that the submatrices corresponding to each variable have rank one. Our methods are algebraic and quite different from those of Lovász and Geelen. We look at the problem of matrix completion in the more general setting of linear spaces of linear transformations and find a maximum rank element there using a greedy method. Matrix algebras and modules play a crucial role in the algorithm. We show (hardness) results for special instances of matrix completion naturally related to matrix algebras; i.e., in contrast to computing isomorphisms of modules (for which there is a known deterministic polynomial time algorithm), finding a surjective or an injective homomorphism between two given modules is as hard as the general matrix completion problem. The same hardness holds for finding a maximum dimension cyclic submodule (i.e., generated by a single element). For the “dual” task, i.e., finding the minimal number of generators of a given module, we present a deterministic polynomial time algorithm. The proof methods developed in this paper apply to fairly general modules and could also be of independent interest.

We show that the rank of a depth-3 circuit (over any field) that is simple, minimal and zero is at most O(k3log d). The previous best rank bound known was 2O(k2)(log d)k-2by Dvir and Shpilka (STOC 2005). This almost resolves the rank question first posed by Dvir and Shpilka (as we also provide a simple and minimal identity of rank Omega(k log d)). Our rank bound significantly improves (dependence on k exponentially reduced) the best known deterministic black-box identity tests for depth-3 circuits by Karnin and Shpilka (CCC 2008). Our techniques also shed light on the factorization pattern of nonzero depth-3 circuits, most strikingly: the rank of linear factors of a simple, minimal and nonzero depth-3 circuit (over any field) is at most O(k3log d). The novel feature of this work is a new notion of maps between sets of linear forms, called ideal matchings, used to study depth-3 circuits. We prove interesting structural results about depth-3 identities using these techniques. We believe that these can lead to the goal of a deterministic polynomial time identity test for these circuits.

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 $\mathsf{U}_2(\mathbb{F})$, the algebra of upper-triangular $2\times 2$ matrices with entries from $\F$. Such a connection is a bit surprising since we also show that, as computational models, $\Pi \Sigma$ circuits over $\mathsf{U}_2(\mathbb{F})$ are strictly `weaker' than $\Sigma \Pi \Sigma$ circuits over $\mathbb{F}$. The equivalence further implies that PIT of $\Sigma \Pi \Sigma$ circuits reduces to PIT of width-$2$ commutative \emph{Algebraic Branching Programs}(ABP). Further, we give a deterministic polynomial time identity testing algorithm for a $\Pi \Sigma$ circuit of size $s$ over commutative algebras of dimension $O(\log s/\log\log s)$ over $\F$. Over commutative algebras of dimension $\poly(s)$, we show that identity testing of $\Pi \Sigma$ circuits is at least as hard as that of $\Sigma \Pi \Sigma$ circuits over $\mathbb{F}$.

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 how the properties of m-schemes relate to improvements in the deterministic complexity of factoring polynomials over finite fields assuming the generalized Riemann Hypothesis (GRH). In particular, we give the first deterministic polynomial time algorithm (assuming GRH) to find a nontrivial factor of a polynomial of prime degree n where (n-1) is a smooth number.

We study the identity testing problem for depth 3 arithmetic circuits (SigmaPiSigma circuit). We give the first deterministic polynomial time identity test for SigmaPiSigma circuits with bounded top fanin. We also show that the rank of a minimal and simple SigmaPiSigma circuit with bounded top fanin, computing zero, can be unbounded. These results answer the open questions posed by Klivans-Spielman (2001) and Dvir-Shpilka (2005)

We study the complexity of the isomorphism and automorphism problems for finite rings. We show that both integer factorization and graph isomorphism reduce to the problem of counting automorphisms of a ring. This counting problem is shown to be in the functional version of the complexity class AM ∩ coAM and hence is not NP-complete unless the polynomial hierarchy collapses. As a “positive” result we show that deciding whether a given ring has a non-trivial automorphism can be done in deterministic polynomial time. Finding such an automorphism is, however, shown to be randomly equivalent to integer factorization.

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 /spl cap/ coAM and hence is not NP-complete unless the polynomial hierarchy collapses. Integer factorization also reduces to the problem of finding nontrivial automorphism of a ring and to the problem of finding isomorphism between two rings. We also show that deciding whether a given ring has a non-trivial automorphism can be done in deterministic polynomial time.