Neeraj Kayal

Principal Researcher

Papiers de Collaboration

Afficher par:

- Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning
  
  Pritam Chandra, Ankit Garg, Neeraj Kayal, Kunal Mittal, Tanmay Sinha
  
  Electronic Colloquium on Computational Complexity, 2023 | November 2023
  
  DOI Publication
- Low-depth arithmetic circuit lower bounds via shifted partials
  
  Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, Bhargav Thankey
  
  Electronic Colloquium on Computational Complexity, 2022 | November 2022
  
  DOI Publication
- Learning sums of powers of low-degree polynomials in the non-degenerate case
  
  Ankit Garg, Neeraj Kayal, Chandan Saha
  
  2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) | April 2020, pp. 889-899
  
  DOI Publication Publication Publication
- An almost Cubic Lower Bound for Depth Three Arithmetic Circuits
  
  Neeraj Kayal, Chandan Saha, Sébastien Tavenas
  
  ICALP 2016 | July 2016
  
  DOI Publication Publication
- Multi-k-ic depth three circuit lower bound
  
  Neeraj Kayal, Chandan Saha
  
  Symposium on Theoretical Aspects of Computer Science (STACS) | March 2015
  
  Symposium on Theoretical Aspects of Computer Science (STACS)
  
  Publication
- An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas
  
  Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan
  
  Foundations of Computer Science (FOCS) | October 2014
  
  Invited to Special Issue of SICOMP journal
  
  Publication
- A super-polynomial lower bound for regular arithmetic formulas.
  
  Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi
  
  Symposium on Theory of Computing (STOC) | June 2014
  
  Symposium on Theory of Computing (STOC)
  
  Publication
- Super-polynomial lower bounds for depth four homogeneous arithmetic formulas
  
  Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan
  
  Symposium on Theory of Computing (STOC) | June 2014
  
  Publication
- A selection of lower bounds for arithmetic circuits
  
  Neeraj Kayal, Ramprasad Saptharishi
  
  Special issue on the occassion of 60th Birthday of Somenath Biswas | Publié par Springer Verlag | 2014 | Special issue on the occassion of 60th Birthday of Somenath Biswas edition
  
  Publication
- Approaching the chasm at depth four
  
  Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi
  
  Conference on Computational Complexity | June 2013
  
  Conference on Computational Complexity
  
  Best Paper Award
  
  Publication
- Random Arithmetic Formulas can be Reconstructed Efficiently
  
  Ankit Gupta, Neeraj Kayal, Youming Qiao
  
  Conference on Computational Complexity | June 2013
  
  Invited to Special Issue of Computational Complexity journal
  
  Publication Publication
- Arithmetic Circuits: A chasm at depth three
  
  Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi
  
  Foundations of Computer Science (FOCS) | March 2013
  
  Invited to Special Issue of SICOMP journal
  
  Publication
- Affine Projections of Polynomials
  
  Neeraj Kayal
  
  Symposium on Theory of Computing (STOC) | January 2012
  
  Publication
- Reconstruction of Depth-4 Multilinear Circuits with Top Fan-in Two
  
  Ankit Gupta, Neeraj Kayal, Satya Lokam
  
  Symposium on Theory of Computing (STOC) | January 2012
  
  Publication
- Efficient Reconstruction of Random Multilinear Formulas
  
  Neeraj Kayal, Ankit Gupta, Satya Lokam
  
  Foundations of Computer Science (FOCS) | October 2011
  
  Publication
- On the Sum of Square Roots of Polynomials and related problems
  
  Neeraj Kayal, Chandan Saha
  
  Conference on Computational Complexity (CCC) | June 2011
  
  Invited to ToCT journal
  
  Publication
- Square root Bound on the Least Power Non-residue using a Sylvester-Vandermonde Determinant
  
  Michael Forbes, Neeraj Kayal, Rajat Mittal, Chandan Saha
  
  April 2011
  
  Publication
- Efficient algorithms for some special cases of the polynomial equivalence problem
  
  Neeraj Kayal
  
  Symposium on Discrete Algorithms (SODA) | January 2011
  
  Publication
- Partial Derivatives in Arithmetic Complexity and beyond
  
  Xi Chen, Neeraj Kayal, Avi Wigderson
  
  Foundations and Trends in Theoretical Computer Science | January 2010
  
  Publication
- Blackbox Polynomial Identity Testing for Depth 3 Circuits
  
  Neeraj Kayal, Shubhangi Saraf
  
  Foundations of Computer Science (FOCS) | January 2009
  
  Foundations of Computer Science (FOCS)
  
  Publication Publication
- Factoring Groups Efficiently
  
  Neeraj Kayal, Timur Nezhmetdinov
  
  International Colloquium on Automata, Languages and Programming (ICALP) | January 2009
  
  ISBN: 978-3-642-02926-4
  
  Publication Publication
- The complexity of the annihilating polynomial
  
  Neeraj Kayal
  
  Conference on Computational Complexity (CCC) | January 2009
  
  Publication
- Complexity of Ring Morphism Problems
  
  Neeraj Kayal, Nitin Saxena
  
  Computational Complexity | June 2006, Vol 15: pp. 342-390
  
  Invited to Special Issue of Computational Complexity Journal
  
  Publication Publication
- Derandomizing some algebraic and number-theoretic algorithms
  
  Neeraj Kayal
  
  January 2006
  
  January 2006
  
  Publication Publication
- Solvability of a System of Bivariate Polynomial Equations over a Finite Field
  
  Neeraj Kayal
  
  International Colloquium on Automata, Languages and Programming (ICALP) | July 2005
  
  ISBN: 3-540-27580-0
  
  Best Student Paper Award
  
  Publication Publication
- Primes is in P
  
  Manindra Agrawal, Neeraj Kayal, Nitin Saxena
  
  Annals of Mathematics | June 2004, Vol 160: pp. 781-793
  
  Godel Prize, Fulkerson Prize
  
  Publication

- Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning
  
  Pritam Chandra, Ankit Garg, Neeraj Kayal, Kunal Mittal, Tanmay Sinha
  
  Electronic Colloquium on Computational Complexity, 2023 | November 2023
  
  DOI Publication
- Low-depth arithmetic circuit lower bounds via shifted partials
  
  Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, Bhargav Thankey
  
  Electronic Colloquium on Computational Complexity, 2022 | November 2022
  
  DOI Publication
- Learning sums of powers of low-degree polynomials in the non-degenerate case
  
  Ankit Garg, Neeraj Kayal, Chandan Saha
  
  2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) | April 2020, pp. 889-899
  
  DOI Publication Publication Publication
- Multi-k-ic depth three circuit lower bound
  
  Neeraj Kayal, Chandan Saha
  
  Symposium on Theoretical Aspects of Computer Science (STACS) | March 2015
  
  Symposium on Theoretical Aspects of Computer Science (STACS)
  
  Publication
- An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas
  
  Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan
  
  Foundations of Computer Science (FOCS) | October 2014
  
  Invited to Special Issue of SICOMP journal
  
  Publication
- Super-polynomial lower bounds for depth four homogeneous arithmetic formulas
  
  Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan
  
  Symposium on Theory of Computing (STOC) | June 2014
  
  Publication
- A super-polynomial lower bound for regular arithmetic formulas.
  
  Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi
  
  Symposium on Theory of Computing (STOC) | June 2014
  
  Symposium on Theory of Computing (STOC)
  
  Publication
- A selection of lower bounds for arithmetic circuits
  
  Neeraj Kayal, Ramprasad Saptharishi
  
  Special issue on the occassion of 60th Birthday of Somenath Biswas | Publié par Springer Verlag | 2014 | Special issue on the occassion of 60th Birthday of Somenath Biswas edition
  
  Publication
- Approaching the chasm at depth four
  
  Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi
  
  Conference on Computational Complexity | June 2013
  
  Conference on Computational Complexity
  
  Best Paper Award
  
  Publication
- Random Arithmetic Formulas can be Reconstructed Efficiently
  
  Ankit Gupta, Neeraj Kayal, Youming Qiao
  
  Conference on Computational Complexity | June 2013
  
  Invited to Special Issue of Computational Complexity journal
  
  Publication Publication
- Arithmetic Circuits: A chasm at depth three
  
  Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi
  
  Foundations of Computer Science (FOCS) | March 2013
  
  Invited to Special Issue of SICOMP journal
  
  Publication
- Affine Projections of Polynomials
  
  Neeraj Kayal
  
  Symposium on Theory of Computing (STOC) | January 2012
  
  Publication
- On the Sum of Square Roots of Polynomials and related problems
  
  Neeraj Kayal, Chandan Saha
  
  Conference on Computational Complexity (CCC) | June 2011
  
  Invited to ToCT journal
  
  Publication
- Efficient algorithms for some special cases of the polynomial equivalence problem
  
  Neeraj Kayal
  
  Symposium on Discrete Algorithms (SODA) | January 2011
  
  Publication
- Blackbox Polynomial Identity Testing for Depth 3 Circuits
  
  Neeraj Kayal, Shubhangi Saraf
  
  Foundations of Computer Science (FOCS) | January 2009
  
  Foundations of Computer Science (FOCS)
  
  Publication Publication
- Factoring Groups Efficiently
  
  Neeraj Kayal, Timur Nezhmetdinov
  
  International Colloquium on Automata, Languages and Programming (ICALP) | January 2009
  
  ISBN: 978-3-642-02926-4
  
  Publication Publication
- Complexity of Ring Morphism Problems
  
  Neeraj Kayal, Nitin Saxena
  
  Computational Complexity | June 2006, Vol 15: pp. 342-390
  
  Invited to Special Issue of Computational Complexity Journal
  
  Publication Publication
- Derandomizing some algebraic and number-theoretic algorithms
  
  Neeraj Kayal
  
  January 2006
  
  January 2006
  
  Publication Publication
- Solvability of a System of Bivariate Polynomial Equations over a Finite Field
  
  Neeraj Kayal
  
  International Colloquium on Automata, Languages and Programming (ICALP) | July 2005
  
  ISBN: 3-540-27580-0
  
  Best Student Paper Award
  
  Publication Publication
- Primes is in P
  
  Manindra Agrawal, Neeraj Kayal, Nitin Saxena
  
  Annals of Mathematics | June 2004, Vol 160: pp. 781-793
  
  Godel Prize, Fulkerson Prize
  
  Publication
- Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning
  
  Pritam Chandra, Ankit Garg, Neeraj Kayal, Kunal Mittal, Tanmay Sinha
  
  Electronic Colloquium on Computational Complexity, 2023 | November 2023
  
  DOI Publication
- Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning
  
  Pritam Chandra, Ankit Garg, Neeraj Kayal, Kunal Mittal, Tanmay Sinha
  
  Electronic Colloquium on Computational Complexity, 2023 | November 2023
  
  DOI Publication
- Learning sums of powers of low-degree polynomials in the non-degenerate case
  
  Ankit Garg, Neeraj Kayal, Chandan Saha
  
  2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) | April 2020, pp. 889-899
  
  DOI Publication Publication Publication
- An almost Cubic Lower Bound for Depth Three Arithmetic Circuits
  
  Neeraj Kayal, Chandan Saha, Sébastien Tavenas
  
  ICALP 2016 | July 2016
  
  DOI Publication Publication
- Reconstruction of Depth-4 Multilinear Circuits with Top Fan-in Two
  
  Ankit Gupta, Neeraj Kayal, Satya Lokam
  
  Symposium on Theory of Computing (STOC) | January 2012
  
  Publication
- Square root Bound on the Least Power Non-residue using a Sylvester-Vandermonde Determinant
  
  Michael Forbes, Neeraj Kayal, Rajat Mittal, Chandan Saha
  
  April 2011
  
  Publication
- Efficient algorithms for some special cases of the polynomial equivalence problem
  
  Neeraj Kayal
  
  Symposium on Discrete Algorithms (SODA) | January 2011
  
  Publication
- The complexity of the annihilating polynomial
  
  Neeraj Kayal
  
  Conference on Computational Complexity (CCC) | January 2009
  
  Publication
- Derandomizing some algebraic and number-theoretic algorithms
  
  Neeraj Kayal
  
  January 2006
  
  January 2006
  
  Publication Publication
- Efficient Reconstruction of Random Multilinear Formulas
  
  Neeraj Kayal, Ankit Gupta, Satya Lokam
  
  Foundations of Computer Science (FOCS) | October 2011
  
  Publication
- Partial Derivatives in Arithmetic Complexity and beyond
  
  Xi Chen, Neeraj Kayal, Avi Wigderson
  
  Foundations and Trends in Theoretical Computer Science | January 2010
  
  Publication

- Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning
  
  Pritam Chandra, Ankit Garg, Neeraj Kayal, Kunal Mittal, Tanmay Sinha
  
  Electronic Colloquium on Computational Complexity, 2023 | November 2023
  
  DOI Publication
- Low-depth arithmetic circuit lower bounds via shifted partials
  
  Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, Bhargav Thankey
  
  Electronic Colloquium on Computational Complexity, 2022 | November 2022
  
  DOI Publication
- Learning sums of powers of low-degree polynomials in the non-degenerate case
  
  Ankit Garg, Neeraj Kayal, Chandan Saha
  
  2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) | April 2020, pp. 889-899
  
  DOI Publication Publication Publication
- Square root Bound on the Least Power Non-residue using a Sylvester-Vandermonde Determinant
  
  Michael Forbes, Neeraj Kayal, Rajat Mittal, Chandan Saha
  
  April 2011
  
  Publication
- Partial Derivatives in Arithmetic Complexity and beyond
  
  Xi Chen, Neeraj Kayal, Avi Wigderson
  
  Foundations and Trends in Theoretical Computer Science | January 2010
  
  Publication
- Complexity of Ring Morphism Problems
  
  Neeraj Kayal, Nitin Saxena
  
  Computational Complexity | June 2006, Vol 15: pp. 342-390
  
  Invited to Special Issue of Computational Complexity Journal
  
  Publication Publication
- Primes is in P
  
  Manindra Agrawal, Neeraj Kayal, Nitin Saxena
  
  Annals of Mathematics | June 2004, Vol 160: pp. 781-793
  
  Godel Prize, Fulkerson Prize
  
  Publication
- An almost Cubic Lower Bound for Depth Three Arithmetic Circuits
  
  Neeraj Kayal, Chandan Saha, Sébastien Tavenas
  
  ICALP 2016 | July 2016
  
  DOI Publication Publication
- Multi-k-ic depth three circuit lower bound
  
  Neeraj Kayal, Chandan Saha
  
  Symposium on Theoretical Aspects of Computer Science (STACS) | March 2015
  
  Symposium on Theoretical Aspects of Computer Science (STACS)
  
  Publication
- An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas
  
  Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan
  
  Foundations of Computer Science (FOCS) | October 2014
  
  Invited to Special Issue of SICOMP journal
  
  Publication
- Super-polynomial lower bounds for depth four homogeneous arithmetic formulas
  
  Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan
  
  Symposium on Theory of Computing (STOC) | June 2014
  
  Publication
- A super-polynomial lower bound for regular arithmetic formulas.
  
  Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi
  
  Symposium on Theory of Computing (STOC) | June 2014
  
  Symposium on Theory of Computing (STOC)
  
  Publication
- Approaching the chasm at depth four
  
  Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi
  
  Conference on Computational Complexity | June 2013
  
  Conference on Computational Complexity
  
  Best Paper Award
  
  Publication
- Random Arithmetic Formulas can be Reconstructed Efficiently
  
  Ankit Gupta, Neeraj Kayal, Youming Qiao
  
  Conference on Computational Complexity | June 2013
  
  Invited to Special Issue of Computational Complexity journal
  
  Publication Publication
- Arithmetic Circuits: A chasm at depth three
  
  Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi
  
  Foundations of Computer Science (FOCS) | March 2013
  
  Invited to Special Issue of SICOMP journal
  
  Publication
- Reconstruction of Depth-4 Multilinear Circuits with Top Fan-in Two
  
  Ankit Gupta, Neeraj Kayal, Satya Lokam
  
  Symposium on Theory of Computing (STOC) | January 2012
  
  Publication
- Affine Projections of Polynomials
  
  Neeraj Kayal
  
  Symposium on Theory of Computing (STOC) | January 2012
  
  Publication
- Efficient Reconstruction of Random Multilinear Formulas
  
  Neeraj Kayal, Ankit Gupta, Satya Lokam
  
  Foundations of Computer Science (FOCS) | October 2011
  
  Publication
- On the Sum of Square Roots of Polynomials and related problems
  
  Neeraj Kayal, Chandan Saha
  
  Conference on Computational Complexity (CCC) | June 2011
  
  Invited to ToCT journal
  
  Publication
- Efficient algorithms for some special cases of the polynomial equivalence problem
  
  Neeraj Kayal
  
  Symposium on Discrete Algorithms (SODA) | January 2011
  
  Publication
- Blackbox Polynomial Identity Testing for Depth 3 Circuits
  
  Neeraj Kayal, Shubhangi Saraf
  
  Foundations of Computer Science (FOCS) | January 2009
  
  Foundations of Computer Science (FOCS)
  
  Publication Publication
- Factoring Groups Efficiently
  
  Neeraj Kayal, Timur Nezhmetdinov
  
  International Colloquium on Automata, Languages and Programming (ICALP) | January 2009
  
  ISBN: 978-3-642-02926-4
  
  Publication Publication
- The complexity of the annihilating polynomial
  
  Neeraj Kayal
  
  Conference on Computational Complexity (CCC) | January 2009
  
  Publication
- Solvability of a System of Bivariate Polynomial Equations over a Finite Field
  
  Neeraj Kayal
  
  International Colloquium on Automata, Languages and Programming (ICALP) | July 2005
  
  ISBN: 3-540-27580-0
  
  Best Student Paper Award
  
  Publication Publication
- A selection of lower bounds for arithmetic circuits
  
  Neeraj Kayal, Ramprasad Saptharishi
  
  Special issue on the occassion of 60th Birthday of Somenath Biswas | Publié par Springer Verlag | 2014 | Special issue on the occassion of 60th Birthday of Somenath Biswas edition
  
  Publication
- Derandomizing some algebraic and number-theoretic algorithms
  
  Neeraj Kayal
  
  January 2006
  
  January 2006
  
  Publication Publication