Neeraj Kayal

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

Collaborative distances:

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

2023

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

Electron. Colloquium Comput. Complex., 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

2021

Learning generalized depth-three arithmetic circuits in the non-degenerate case.

Vishwas Bhargava, Ankit Garg, Neeraj Kayal, Chandan Saha

Electron. Colloquium Comput. Complex., 2021

2020

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

Ankit Garg, Neeraj Kayal, Chandan Saha

Electron. Colloquium Comput. Complex., 2020

2019

Determinant equivalence test over finite fields and over ℚ.

Ankit Garg, Nikhil Gupta, Neeraj Kayal, Chandan Saha

Electron. Colloquium Comput. Complex., 2019

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

Neeraj Kayal, Vineet Nair, Chandan Saha

Comput. Complex., 2019

2018

Guest Column: A Paradigm for Arithmetic Circuit Lower Bounds.

Neeraj Kayal, Chandan Saha

SIGACT News, 2018

Reconstruction of non-degenerate homogeneous depth three circuits.

Neeraj Kayal, Chandan Saha

Electron. Colloquium Comput. Complex., 2018

2017

An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas.

Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan

SIAM J. Comput., 2017

Multi-k-ic Depth Three Circuit Lower Bound.

Neeraj Kayal, Chandan Saha

Theory Comput. Syst., 2017

Reconstruction of full rank Algebraic Branching Programs.

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

Electron. Colloquium Comput. Complex., 2017

Unexpected power of low-depth arithmetic circuits.

Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi

Commun. ACM, 2017

2016

Arithmetic Circuits: A Chasm at Depth 3.

Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi

SIAM J. Comput., 2016

An almost Cubic Lower Bound for Depth Three Arithmetic Circuits.

Neeraj Kayal, Chandan Saha, Sébastien Tavenas

Electron. Colloquium Comput. Complex., 2016

Lower Bounds for Depth-Three Arithmetic Circuits with small bottom fanin.

Neeraj Kayal, Chandan Saha

Comput. Complex., 2016

2015

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

Neeraj Kayal, Chandan Saha, Sébastien Tavenas

Electron. Colloquium Comput. Complex., 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

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

Neeraj Kayal, Vineet Nair, Chandan Saha

Electron. Colloquium Comput. Complex., 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

2014

Approaching the Chasm at Depth Four.

Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi

J. ACM, 2014

Random arithmetic formulas can be reconstructed efficiently.

Ankit Gupta, Neeraj Kayal, Youming Qiao

Comput. Complex., 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

2013

A super-polynomial lower bound for regular arithmetic formulas.

Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi

Electron. Colloquium Comput. Complex., 2013

Arithmetic circuits: A chasm at depth three.

Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi

Electron. Colloquium Comput. Complex., 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

2010

On the Sum of Square Roots of Polynomials and related problems.

Neeraj Kayal, Chandan Saha

Electron. Colloquium Comput. Complex., 2010

Algorithms for Arithmetic Circuits.

Neeraj Kayal

Electron. Colloquium Comput. Complex., 2010

2009

Blackbox Polynomial Identity Testing for Depth 3 Circuits.

Neeraj Kayal, Shubhangi Saraf

Electron. Colloquium Comput. Complex., 2009

The Complexity of the Annihilating Polynomial.

Neeraj Kayal

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

2008

Factoring groups efficiently.

Neeraj Kayal, Timur Nezhmetdinov

Electron. Colloquium Comput. Complex., 2008

2007

Polynomial Identity Testing for Depth 3 Circuits.

Neeraj Kayal, Nitin Saxena

Comput. Complex., 2007

2006

Complexity of Ring Morphism Problems.

Neeraj Kayal, Nitin Saxena

Comput. Complex., 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