Neeraj Kayal

Publications

## 2013

- Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi, Arithmetic Circuits: A chasm at depth three, in
*Foundations of Computer Science (FOCS)*, IEEE, 2013. - Ankit Gupta, Neeraj Kayal, and Youming Qiao, Random Arithmetic Formulas can be Reconstructed Efficiently, in
*Conference on Computational Complexity*, IEEE, 2013. - Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi, Approaching the chasm at depth four, in
*Conference on Computational Complexity*, IEEE, 2013.

## 2012

- Ankit Gupta, Neeraj Kayal, and Satya Lokam, Reconstruction of Depth-4 Multilinear Circuits with top fanin two, in
*Symposium on Theory of Computing (STOC)*, ACM, 2012. - Neeraj Kayal, Affine Projections of Polynomials, in
*Symposium on Theory of Computing (STOC)*, ACM, 2012.

## 2011

- Neeraj Kayal and Chandan Saha, On the Sum of Square Roots of Polynomials and related problems, in
*Conference on Computational Complexity (CCC)*, IEEE, 2011. - Ankit Gupta, Neeraj Kayal, and Satya Lokam, Efficient Reconstruction of Random Multilinear Formulas, in
*Foundations of Computer Science (FOCS)*, IEEE, 2011. - Neeraj Kayal, Efficient algorithms for some special cases of the polynomial equivalence problem, in
*Symposium on Discrete Algorithms (SODA)*, Society for Industrial and Applied Mathematics, 2011.

## 2009

- Neeraj Kayal and Timur Nezhmetdinov, Factoring Groups Efficiently, in
*International Colloquium on Automata, Languages and Programming (ICALP)*, Springer Verlag, 2009. - Neeraj Kayal, The complexity of the annihilating polynomial, in
*Conference on Computational Complexity (CCC)*, IEEE, 2009. - Neeraj Kayal and Shubhangi Saraf, Blackbox Polynomial Identity Testing for Depth 3 Circuits, in
*Foundations of Computer Science (FOCS)*, IEEE, 2009.

## 2007

- Neeraj Kayal and Nitin Saxena, Polynomial Identity Testing for Depth 3 Circuits, in
*Computational Complexity*, vol. 16, no. 2, pp. 115-138, Springer Verlag, 2007.

## 2006

- Neeraj Kayal and Nitin Saxena, Complexity of Ring Morphism Problems, in
*Computational Complexity*, vol. 15, no. 4, pp. 342-390, 2006.

## 2005

- Neeraj Kayal, Solvability of a System of Bivariate Polynomial Equations over a Finite Field, in
*International Colloquium on Automata, Languages and Programming (ICALP)*, Springer, 2005.

## 2004

- Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, Primes is in P, in
*Annals of Mathematics*, vol. 160, no. 2, pp. 781-793, 2004.