Research



Surveys

Progress on Polynomial Identity Testing-II.
Proceedings of the Workshop celebrating Somenath Biswas' 60th Birthday,
December 2013. [pdf]


Progress on Polynomial Identity Testing.
Bulletin of the EATCS, no.99, 49-79, October 2009. [pdf]


Proceedings & Journals


Discovering the roots: Uniform closure results for algebraic classes under factoring
with Pranjal Dutta and Amit Sinhababu
submitted, 2017. [pdf]


Small hitting-sets for tiny algebraic circuits or: How to turn bad designs into good
with Manindra Agrawal, Michael A. Forbes and Sumanta Ghosh
submitted, 2017. [pdf]


Irreducibility and deterministic r-th root finding over finite fields

with Vishwas Bhargava, Gábor Ivanyos and Rajat Mittal
42nd International Symposium on Symbolic and Algebraic Computation (ISSAC), 2017. [pdf]


Polynomial Interpolation and Identity Testing from High Powers Over Finite Fields
with Gábor Ivanyos, Marek Karpinski, Miklos Santha and Igor E. Shparlinski
Algorithmica, DOI 10.1007/s00453-016-0273-1, 2017. [pdf]


Algebraic independence over positive characteristic: New criterion and applications to locally low algebraic rank circuits
with Anurag Pandey and Amit Sinhababu
MFCS, 74:1-74:15, 2016. [pdf] [full]


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), 6:1-6:14, 2016. [pdf]

Deterministic Identity Testing for Sum of ROABPs
with Rohit Gurjar, Arpita Korwar and Thomas Thierauf
Computational Complexity Conference, 2015. [pdf]
(Journal of Computational Complexity, DOI 10.1007/s00037-016-0141-z, 2016. [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-D Formulas
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., vol.81, 493-531, 2012. [pdf]


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]


Manuscripts

PhD Thesis. [pdf]

On the centers of higher degree forms. [pdf]