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)
Neeraj Kayal
Principal Researcher
Publications
Publications by Year
-
-
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
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)
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
A selection of lower bounds for arithmetic circuits
Neeraj Kayal, Ramprasad Saptharishi
Special issue on the occassion of 60th Birthday of Somenath Biswas | Published by Springer Verlag | 2014 | Special issue on the occassion of 60th Birthday of Somenath Biswas edition
-
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
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
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
-
Affine Projections of Polynomials
Symposium on Theory of Computing (STOC) | January 2012
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
-
Efficient Reconstruction of Random Multilinear Formulas
Neeraj Kayal, Ankit Gupta, Satya Lokam
Foundations of Computer Science (FOCS) | October 2011
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
Square root Bound on the Least Power Non-residue using a Sylvester-Vandermonde Determinant
Michael Forbes, Neeraj Kayal, Rajat Mittal, Chandan Saha
April 2011
Efficient algorithms for some special cases of the polynomial equivalence problem
Symposium on Discrete Algorithms (SODA) | January 2011
Efficient Reconstruction of Random Multilinear Formulas
Neeraj Kayal, Ankit Gupta, Satya Lokam
Foundations of Computer Science (FOCS) | January 2011
-
Partial Derivatives in Arithmetic Complexity and beyond
Xi Chen, Neeraj Kayal, Avi Wigderson
Foundations and Trends in Theoretical Computer Science | January 2010
-
Blackbox Polynomial Identity Testing for Depth 3 Circuits
Neeraj Kayal, Shubhangi Saraf
Foundations of Computer Science (FOCS) | January 2009
Foundations of Computer Science (FOCS)
Factoring Groups Efficiently
Neeraj Kayal, Timur Nezhmetdinov
International Colloquium on Automata, Languages and Programming (ICALP) | January 2009
ISBN: 978-3-642-02926-4
The complexity of the annihilating polynomial
Conference on Computational Complexity (CCC) | January 2009
-
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
Derandomizing some algebraic and number-theoretic algorithms
January 2006
January 2006
-
Solvability of a System of Bivariate Polynomial Equations over a Finite Field
International Colloquium on Automata, Languages and Programming (ICALP) | July 2005
ISBN: 3-540-27580-0
Best Student Paper Award
-
Primes is in P
Manindra Agrawal, Neeraj Kayal, Nitin Saxena
Annals of Mathematics | June 2004, Vol 160: pp. 781-793
Godel Prize, Fulkerson Prize
Publications by Research Area
-
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
Square root Bound on the Least Power Non-residue using a Sylvester-Vandermonde Determinant
Michael Forbes, Neeraj Kayal, Rajat Mittal, Chandan Saha
April 2011
Efficient Reconstruction of Random Multilinear Formulas
Neeraj Kayal, Ankit Gupta, Satya Lokam
Foundations of Computer Science (FOCS) | January 2011
Efficient algorithms for some special cases of the polynomial equivalence problem
Symposium on Discrete Algorithms (SODA) | January 2011
The complexity of the annihilating polynomial
Conference on Computational Complexity (CCC) | January 2009
Derandomizing some algebraic and number-theoretic algorithms
January 2006
January 2006
-
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)
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
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
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)
A selection of lower bounds for arithmetic circuits
Neeraj Kayal, Ramprasad Saptharishi
Special issue on the occassion of 60th Birthday of Somenath Biswas | Published by Springer Verlag | 2014 | Special issue on the occassion of 60th Birthday of Somenath Biswas edition
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
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
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
Affine Projections of Polynomials
Symposium on Theory of Computing (STOC) | January 2012
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
Efficient algorithms for some special cases of the polynomial equivalence problem
Symposium on Discrete Algorithms (SODA) | January 2011
Factoring Groups Efficiently
Neeraj Kayal, Timur Nezhmetdinov
International Colloquium on Automata, Languages and Programming (ICALP) | January 2009
ISBN: 978-3-642-02926-4
Blackbox Polynomial Identity Testing for Depth 3 Circuits
Neeraj Kayal, Shubhangi Saraf
Foundations of Computer Science (FOCS) | January 2009
Foundations of Computer Science (FOCS)
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
Derandomizing some algebraic and number-theoretic algorithms
January 2006
January 2006
Solvability of a System of Bivariate Polynomial Equations over a Finite Field
International Colloquium on Automata, Languages and Programming (ICALP) | July 2005
ISBN: 3-540-27580-0
Best Student Paper Award
Primes is in P
Manindra Agrawal, Neeraj Kayal, Nitin Saxena
Annals of Mathematics | June 2004, Vol 160: pp. 781-793
Godel Prize, Fulkerson Prize
-
Efficient Reconstruction of Random Multilinear Formulas
Neeraj Kayal, Ankit Gupta, Satya Lokam
Foundations of Computer Science (FOCS) | October 2011
-
Partial Derivatives in Arithmetic Complexity and beyond
Xi Chen, Neeraj Kayal, Avi Wigderson
Foundations and Trends in Theoretical Computer Science | January 2010
Publications by Type
-
Square root Bound on the Least Power Non-residue using a Sylvester-Vandermonde Determinant
Michael Forbes, Neeraj Kayal, Rajat Mittal, Chandan Saha
April 2011
Partial Derivatives in Arithmetic Complexity and beyond
Xi Chen, Neeraj Kayal, Avi Wigderson
Foundations and Trends in Theoretical Computer Science | January 2010
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
Primes is in P
Manindra Agrawal, Neeraj Kayal, Nitin Saxena
Annals of Mathematics | June 2004, Vol 160: pp. 781-793
Godel Prize, Fulkerson Prize
-
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)
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
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
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)
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
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
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
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
Affine Projections of Polynomials
Symposium on Theory of Computing (STOC) | January 2012
Efficient Reconstruction of Random Multilinear Formulas
Neeraj Kayal, Ankit Gupta, Satya Lokam
Foundations of Computer Science (FOCS) | October 2011
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
Efficient Reconstruction of Random Multilinear Formulas
Neeraj Kayal, Ankit Gupta, Satya Lokam
Foundations of Computer Science (FOCS) | January 2011
Efficient algorithms for some special cases of the polynomial equivalence problem
Symposium on Discrete Algorithms (SODA) | January 2011
The complexity of the annihilating polynomial
Conference on Computational Complexity (CCC) | January 2009
Factoring Groups Efficiently
Neeraj Kayal, Timur Nezhmetdinov
International Colloquium on Automata, Languages and Programming (ICALP) | January 2009
ISBN: 978-3-642-02926-4
Blackbox Polynomial Identity Testing for Depth 3 Circuits
Neeraj Kayal, Shubhangi Saraf
Foundations of Computer Science (FOCS) | January 2009
Foundations of Computer Science (FOCS)
Solvability of a System of Bivariate Polynomial Equations over a Finite Field
International Colloquium on Automata, Languages and Programming (ICALP) | July 2005
ISBN: 3-540-27580-0
Best Student Paper Award
-
A selection of lower bounds for arithmetic circuits
Neeraj Kayal, Ramprasad Saptharishi
Special issue on the occassion of 60th Birthday of Somenath Biswas | Published by Springer Verlag | 2014 | Special issue on the occassion of 60th Birthday of Somenath Biswas edition
-
Derandomizing some algebraic and number-theoretic algorithms
January 2006
January 2006