Manindra Agrawal

STOC Conference 2018 Conference Paper

Bootstrapping variables in algebraic circuits

• Manindra Agrawal
• Sumanta Ghosh
• Nitin Saxena 0001

MFCS Conference 2016 Conference Paper

Integer Factoring Using Small Algebraic Dependencies

• Manindra Agrawal
• Nitin Saxena 0001
• Shubham Sahai Srivastava

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<q are primes, we exploit the difference in the two Frobenius morphisms (one over F_p and the other over F_q) to factor n in special cases. Specifically, our algorithm is polynomial time (on number theoretic conjectures) if we know a small algebraic dependence between p, q. We discuss families of n where our algorithm is significantly faster than the algorithms based on known techniques.

TCS Journal 2014 Journal Article

Theory and Applications of Models of Computation at the Turing Centenary in China

• George Barmpalias
• Manindra Agrawal
• S. Barry Cooper

STOC Conference 2013 Conference Paper

Quasi-polynomial hitting-set for set-depth-Δ formulas

• Manindra Agrawal
• Chandan Saha 0001
• Nitin Saxena 0001

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(term{x})=∑ i=1 k ∏ j=1 d f i,j (term{x} X j ), where f i,j is a sparse polynomial in F[term{x} X j ]. 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((D 2 log 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.

STOC Conference 2012 Conference Paper

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

• Manindra Agrawal
• Chandan Saha 0001
• Ramprasad Saptharishi
• Nitin Saxena 0001

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. 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 - that is equally effective in solving both the problems on certain interesting and previously well-investigated (but not well understood) models of computation.

TCS Journal 2011 Journal Article

Theory and applications of models of computation (TAMC 2008)

• Manindra Agrawal
• Angsheng Li

FOCS Conference 2008 Conference Paper

Arithmetic Circuits: A Chasm at Depth Four

• Manindra Agrawal
• V. Vinay

We show that proving exponential lower bounds on depth four arithmetic circuits imply exponential lower bounds for unrestricted depth arithmetic circuits. In other words, for exponential sized circuits additional depth beyond four does not help. We then show that a complete black-box derandomization of identity testing problem for depth four circuits with multiplication gates of small fanin implies a nearly complete derandomization of general identity testing.

FOCS Conference 1999 Conference Paper

Primality and Identity Testing via Chinese Remaindering

• Manindra Agrawal
• Somenath Biswas

Gives a simple and new primality testing algorithm by reducing primality testing for a number n to testing if a specific univariate identity over Z/sub n/ holds. We also give new randomized algorithms for testing if a multivariate polynomial, over a finite field or over rationals, is identically zero. The first of these algorithms also works over Z/sub n/ for any n. The running time of the algorithms is polynomial in the size of the arithmetic circuit representing the input polynomial and the error parameter. These algorithms use fewer random bits and work for a larger class of polynomials than all the previously known methods, e. g. the Schwartz-Zippel test (J. T. Schwartz, 1980; R. E. Zippel, 1979), the Chen-Kao (1997) test and the Lewin-Vadhan (1998) test. Our algorithms first transform the input polynomial to a univariate polynomial and then use Chinese remaindering over univariate polynomials to effectively test if it is zero.

STOC Conference 1997 Conference Paper

Reducing the Complexity of Reductions

• Manindra Agrawal
• Eric Allender
• Russell Impagliazzo
• Toniann Pitassi
• Steven Rudich

FOCS Conference 1996 Conference Paper

The Boolean Isomorphism Problem

• Manindra Agrawal
• Thomas Thierauf

We investigate the computational complexity of the Boolean isomorphism problem (BI): on input of two Boolean formulas F and G decide whether there exists a permutation of the variables of G such that F and G become equivalent. Our main result is a one-round interactive proof for BI, where the verifier has access to an NP oracle. To obtain this, we use a recent result from learning theory by N. Bshouty et al. (1995), that Boolean formulas can be learned probabilistically with equivalence queries and access to an NP oracle. As a consequence, BI cannot be /spl Sigma//sub 2//sup p/ complete unless the polynomial hierarchy collapses. This solves an open problem posed previously. Further properties of BI are shown: BI has And- and Or-functions, the counting version, BI, can be computed in polynomial time relative to BI, and BI is self-reducible.