Neeraj Kayal

According to our database, Neeraj Kayal authored at least 48 papers between 2004 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

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

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

2023

Low-Depth Arithmetic Circuit Lower Bounds: Bypassing Set-Multilinearization.

Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, Bhargav Thankey

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

2022

Low-depth arithmetic circuit lower bounds via shifted partials.

Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, Bhargav Thankey

Electron. Colloquium Comput. Complex., 2022

Learning Generalized Depth Three Arithmetic Circuits in the Non-Degenerate Case.

Vishwas Bhargava, Ankit Garg, Neeraj Kayal, Chandan Saha

Proceedings of the Approximation, 2022

2020

Learning sums of powers of low-degree polynomials in the non-degenerate case.

Ankit Garg, Neeraj Kayal, Chandan Saha

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Average-case linear matrix factorization and reconstruction of low width algebraic branching programs.

Neeraj Kayal, Vineet Nair, Chandan Saha

Comput. Complex., 2019

Reconstruction of non-degenerate homogeneous depth three circuits.

Neeraj Kayal, Chandan Saha

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Determinant Equivalence Test over Finite Fields and over Q.

Ankit Garg, Nikhil Gupta, Neeraj Kayal, Chandan Saha

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018

Guest Column: A Paradigm for Arithmetic Circuit Lower Bounds.

Neeraj Kayal, Chandan Saha

SIGACT News, 2018

2017

Unexpected power of low-depth arithmetic circuits.

Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi

Commun. ACM, 2017

Reconstruction of Full Rank Algebraic Branching Programs.

Neeraj Kayal, Vineet Nair, Chandan Saha, Sébastien Tavenas

Proceedings of the 32nd Computational Complexity Conference, 2017

2016

Arithmetic Circuits: A Chasm at Depth 3.

Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi

SIAM J. Comput., 2016

On the size of homogeneous and of depth four formulas with low individual degree.

Neeraj Kayal, Chandan Saha, Sébastien Tavenas

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits.

Neeraj Kayal, Vineet Nair, Chandan Saha

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

An Almost Cubic Lower Bound for Depth Three Arithmetic Circuits.

Neeraj Kayal, Chandan Saha, Sébastien Tavenas

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

Lower Bounds for Sums of Products of Low arity Polynomials.

Neeraj Kayal, Chandan Saha

Electron. Colloquium Comput. Complex., 2015

Multi-<i>k</i>-ic depth three circuit lower bound.

Neeraj Kayal, Chandan Saha

Electron. Colloquium Comput. Complex., 2015

Multi-k-ic Depth Three Circuit Lower Bound.

Neeraj Kayal, Chandan Saha

Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

Lower Bounds for Sums of Powers of Low Degree Univariates.

Neeraj Kayal, Pascal Koiran, Timothée Pecatte, Chandan Saha

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Lower Bounds for Depth Three Arithmetic Circuits with Small Bottom Fanin.

Neeraj Kayal, Chandan Saha

Proceedings of the 30th Conference on Computational Complexity, 2015

2014

A super-polynomial lower bound for regular arithmetic formulas.

Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi

Proceedings of the Symposium on Theory of Computing, 2014

Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas.

Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan

Proceedings of the Symposium on Theory of Computing, 2014

Arithmetic Circuit Complexity (Tutorial).

Neeraj Kayal

Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas.

Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

Arithmetic Circuits: A Chasm at Depth Three.

Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Random Arithmetic Formulas Can Be Reconstructed Efficiently.

Ankit Gupta, Neeraj Kayal, Youming Qiao

Proceedings of the 28th Conference on Computational Complexity, 2013

Approaching the Chasm at Depth Four.

Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi

Proceedings of the 28th Conference on Computational Complexity, 2013

2012

An exponential lower bound for the sum of powers of bounded degree polynomials.

Neeraj Kayal

Electron. Colloquium Comput. Complex., 2012

An exponential lower bound for homogeneous depth four arithmetic circuits with bounded bottom fanin.

Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi

Electron. Colloquium Comput. Complex., 2012

Affine projections of polynomials: extended abstract.

Neeraj Kayal

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Reconstruction of depth-4 multilinear circuits with top fan-in 2.

Ankit Gupta, Neeraj Kayal, Satyanarayana V. Lokam

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

2011

Partial Derivatives in Arithmetic Complexity and Beyond.

Xi Chen, Neeraj Kayal, Avi Wigderson

Found. Trends Theor. Comput. Sci., 2011

Affine projections of polynomials.

Neeraj Kayal

Electron. Colloquium Comput. Complex., 2011

Reconstruction of Depth-4 Multilinear Circuits with Top fanin 2.

Ankit Gupta, Neeraj Kayal, Satyanarayana V. Lokam

Electron. Colloquium Comput. Complex., 2011

Square root Bound on the Least Power Non-residue using a Sylvester-Vandermonde Determinant

Michael Forbes, Neeraj Kayal, Rajat Mittal, Chandan Saha

CoRR, 2011

Efficient algorithms for some special cases of the polynomial equivalence problem.

Neeraj Kayal

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Efficient Reconstruction of Random Multilinear Formulas.

Ankit Gupta, Neeraj Kayal, Satyanarayana V. Lokam

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

On the Sum of Square Roots of Polynomials and Related Problems.

Neeraj Kayal, Chandan Saha

Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011

2010

Algorithms for Arithmetic Circuits.

Neeraj Kayal

Electron. Colloquium Comput. Complex., 2010

2009

Factoring Groups Efficiently.

Neeraj Kayal, Timur Nezhmetdinov

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

Blackbox Polynomial Identity Testing for Depth 3 Circuits.

Neeraj Kayal, Shubhangi Saraf

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

The Complexity of the Annihilating Polynomial.

Neeraj Kayal

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

2006

Complexity of Ring Morphism Problems.

Neeraj Kayal, Nitin Saxena

Comput. Complex., 2006

Polynomial Identity Testing for Depth 3 Circuits.

Neeraj Kayal, Nitin Saxena

Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

2005

Recognizing permutation functions in polynomial time.

Neeraj Kayal

Electron. Colloquium Comput. Complex., 2005

Solvability of a System of Bivariate Polynomial Equations over a Finite Field.

Neeraj Kayal

Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

On the Ring Isomorphism and Automorphism Problems.

Neeraj Kayal, Nitin Saxena

Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004

On the Ring Isomorphism & Automorphism Problems

Neeraj Kayal, Nitin Saxena

Electron. Colloquium Comput. Complex., 2004