Research in theoretical computer science

with Meena Mahajan and Madhavan Mukund

Progress on Polynomial Identity Testing-II.

Proceedings of the Workshop celebrating Somenath Biswas' 60th Birthday, Perspectives in Computational Complexity, vol.26 of Progress in Computer Science and Applied Logic, 131-146, 2014. (Invited by the editor). [pdf]

Progress on Polynomial Identity Testing.

Bulletin of the EATCS, no.99, 49-79, October 2009. (Invited by the editor). [pdf]

submitted, 2020. [pdf]

14th Biannual Algorithmic Number Theory Symposium, ANTS-XIV, 2020. [pdf]

submitted, 2020. [pdf] [webinar]

Poly-time blackbox identity testing for sum of log-variate constant-width ROABPs

submitted, 2020. [pdf] [webinar]

45th International Symposium on Symbolic and Algebraic Computation (ISSAC), 2020. [pdf]

Counting basic-irreducible factors mod p

34th Computational Complexity Conference (CCC), 2019. [pdf]

Efficiently factoring polynomials modulo p

44th International Symposium on Symbolic and Algebraic Computation (ISSAC), 2019. [pdf]

with Michael A.Forbes and Sumanta Ghosh

Algebraic dependencies and PSPACE algorithms in approximative complexity over any field

with Zeyu Guo and Amit Sinhababu

33rd Computational Complexity Conference (CCC), 2018. [pdf]

(Invited in the special issue of the journal ToC, vol.15(16), 1--30, 2019. [pdf])

with Pranjal Dutta and Amit Sinhababu

50th ACM Symposium on Theory of Computing (STOC), 2018. [full] [conf]

50th ACM Symposium on Theory of Computing (STOC), 2018. [full]

(Article in Proceedings of the National Academy of Sciences of the USA, PNAS, 2019. [pdf])

Irreducibility and deterministic r-th root finding over finite fields

42nd International Symposium on Symbolic and Algebraic Computation (ISSAC), 37--44, 2017. [pdf]

Algorithmica, 80(2), 560-575, 2018. [pdf]

MFCS, 58, 74:1-74:15, 2016. [pdf]

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

with Rohit Gurjar and Arpita Korwar

Computational Complexity Conference, 29:1-29:16, 2016. [pdf]

(Invited in the special issue of the journal ToC, Volume 13 (999), 2017, pp. 1–21. [pdf])

**Integer factoring using small
algebraic dependencies**

with Manindra Agrawal and Shubham Sahai Srivastava

41st International Symposium on
Mathematical Foundations of Computer Science (MFCS), 58, 6:1-6:14, 2016. [pdf]

Deterministic Identity Testing
for Sum of ROABPs

with Rohit Gurjar, Arpita Korwar and Thomas Thierauf

Computational Complexity
Conference, 33, 323-346, 2015. [pdf]

(Journal of Computational
Complexity, 26(4), 835-880, 2017. [pdf])

Hitting-sets for ROABP and sum
of set-multilinear circuits

with Manindra Agrawal, Rohit Gurjar and Arpita Korwar

SICOMP, vol.44, no.3, 669-697, 2015. [pdf]

(Subsumes an older preprint, 2013 [pdf])

Quasi-polynomial Hitting-set for Set-depth-

with Manindra Agrawal and Chandan Saha

45th ACM Symposium on Theory of Computing (STOC), pp.321-330, 2013. [eccc] [conf]

Deterministic Polynomial Factoring and Association Schemes

with Manuel Arora, Gábor Ivanyos and Marek Karpinski.

LMS J. Comput. Math., vol.17, no.1, 123-140, 2014. [pdf]

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

with Johannes Mittmann and Peter Scheiblechner.

Trans. Amer. Math. Soc., vol.366, no.7, 3425-3450, 2014. [pdf]

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

with Manindra Agrawal, Chandan Saha and Ramprasad Saptharishi.

44th ACM Symposium on Theory of Computing (STOC), pp.599-614, 2012. [pdf]

(invited in the special issue of the journal SICOMP, vol. 45, No. 4, pp. 1533–1562, 2016. [pdf])

Algebraic Independence and Blackbox Identity Testing

with Malte Beecken and Johannes Mittmann.

38th International Colloquium on Automata, Languages and Programming (ICALP), pp.137-148, 2011. [pdf]

[Awarded the Best Paper in Track A]

(invited and accepted in the special issue of the journal Information & Computation, vol.222, 2-19, 2013. [pdf])

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

with Chandan Saha and Ramprasad Saptharishi.

Computational Complexity, vol.22, no.1, 39-69, 2013. [pdf]

Blackbox Identity Testing for Bounded Top Fanin Depth-3 Circuits: the field doesn't matter

with C. Seshadhri.

43rd ACM Symposium on Theory of Computing (STOC), pp.431-440, 2011. [pdf]

(invited and accepted in the special issue of the journal SIAM J. Comput., vol.41, no.5, 1285-1298, 2012. [pdf])

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

with C. Seshadhri.

51st Annual IEEE Symposium on
Foundations of Computer Science (FOCS), pp.21-29, 2010. [conf]

(Journal of the ACM, vol.60, no.5, article 33,
2013. [full])

Deterministic Polynomial Time Algorithms for Matrix Completion Problems.

with Gábor Ivanyos and Marek Karpinski.

SIAM J. Comp., vol.39, no.8, 3736-3751, 2010. [pdf]

The Power of Depth 2 Circuits over Algebras.

with Chandan Saha and Ramprasad Saptharishi.

29th Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pp.371-382, 2009. [pdf]

An Almost Optimal Rank Bound for Depth-3 Identities.

with C. Seshadhri.

24th IEEE Conference on Computational Complexity (CCC), pp.137-148, 2009. [pdf]

(longer version in SICOMP, vol.40, no.1, 200-224, 2011. [pdf])

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

with Gábor Ivanyos, Marek Karpinski and Lajos Rónyai.

Math. Comp.,

Schemes for Deterministic Polynomial Factoring.

with Gábor Ivanyos and Marek Karpinski.

34th International Symposium on Symbolic and Algebraic Computation (ISSAC), pp.191-198, 2009. [pdf]

Diagonal Circuit Identity Testing and Lower Bounds.

35th International Colloquium on Automata, Languages and Programming (ICALP), LNCS 5125, pp.60-71, 2008. [pdf]

Parameters of Integral Circulant Graphs and Periodic Quantum Dynamics.

with Simone Severini and Igor E. Shparlinski.

International Journal of Quantum Information, volume 5(3), 417-430, 2007. [pdf]

Polynomial Identity Testing for Depth 3 Circuits.

with Neeraj Kayal.

21st IEEE Conference on Computational Complexity (CCC), pp.9-17, 2006. [pdf]

[Awarded the Best Paper and Best Student Paper Awards]

(invited in the special issue of the journal Computational Complexity, volume 16(2), 115-138, 2007. [pdf])

Equivalence of F-algebras and cubic forms.

with Manindra Agrawal.

23rd STACS, Springer LNCS 3884, pp.115-126, 2006. [pdf]

(full version [pdf])

Automorphisms of Finite Rings and Applications to Complexity of Problems.

with Manindra Agrawal.

22nd Symposium on Theoretical Aspects of Computer Science (STACS), Springer LNCS 3404, pp.1-17, 2005. [pdf]

On the Ring Isomorphism & Automorphism Problems.

with Neeraj Kayal.

20th IEEE Conference on Computational Complexity (CCC), pp.2-12, 2005. [pdf]

(invited in the special issue of the journal Computational Complexity, volume 15(4), 342-390, 2006. [pdf])

PRIMES is in P. [original version]

with Manindra Agrawal, Neeraj Kayal.

Annals of Mathematics, volume 160(2), 781-793, 2004. [pdf]

[Awarded Gödel Prize 2006 and Fulkerson Prize 2006]

On the centers of higher degree forms. [pdf]