Neeraj Kayal

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 | Published by 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 | Published by 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 | Published by 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