Neeraj Kayal

Publication Activity (10 Years)

Years Active: 2004-2024
Publications (10 Years): 32

Top Topics

Quantifier Free

Scaled Orthographic

Top Venues

Electron. Colloquium Comput. Complex.

Publications

Pritam Chandra, Ankit Garg, Neeraj Kayal, Kunal Mittal, Tanmay Sinha
Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning. ITCS (2024)
Pritam Chandra, Ankit Garg, Neeraj Kayal, Kunal Mittal, Tanmay Sinha
Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning. Electron. Colloquium Comput. Complex. (2023)
Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, Bhargav Thankey
Low-Depth Arithmetic Circuit Lower Bounds: Bypassing Set-Multilinearization. ICALP (2023)
Pritam Chandra, Ankit Garg, Neeraj Kayal, Kunal Mittal, Tanmay Sinha
Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning. CoRR (2023)
Vishwas Bhargava, Ankit Garg, Neeraj Kayal, Chandan Saha
Learning Generalized Depth Three Arithmetic Circuits in the Non-Degenerate Case. APPROX/RANDOM (2022)
Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, Bhargav Thankey
Low-depth arithmetic circuit lower bounds via shifted partials. Electron. Colloquium Comput. Complex. (2022)
Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, Bhargav Thankey
Low-depth arithmetic circuit lower bounds via shifted partials. CoRR (2022)
Vishwas Bhargava, Ankit Garg, Neeraj Kayal, Chandan Saha
Learning generalized depth-three arithmetic circuits in the non-degenerate case. Electron. Colloquium Comput. Complex. 28 (2021)
Ankit Garg, Neeraj Kayal, Chandan Saha
Learning sums of powers of low-degree polynomials in the non-degenerate case. CoRR (2020)
Ankit Garg, Neeraj Kayal, Chandan Saha
Learning sums of powers of low-degree polynomials in the non-degenerate case. FOCS (2020)
Ankit Garg, Neeraj Kayal, Chandan Saha
Learning sums of powers of low-degree polynomials in the non-degenerate case. Electron. Colloquium Comput. Complex. 27 (2020)
Neeraj Kayal, Vineet Nair, Chandan Saha
Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth-three Circuits. ACM Trans. Comput. Theory 12 (1) (2020)
Neeraj Kayal, Chandan Saha
Reconstruction of non-degenerate homogeneous depth three circuits. STOC (2019)
Neeraj Kayal, Vineet Nair, Chandan Saha, Sébastien Tavenas
Reconstruction of Full Rank Algebraic Branching Programs. ACM Trans. Comput. Theory 11 (1) (2019)
Ankit Garg, Nikhil Gupta, Neeraj Kayal, Chandan Saha
Determinant Equivalence Test over Finite Fields and over Q. ICALP (2019)
Neeraj Kayal, Vineet Nair, Chandan Saha
Average-case linear matrix factorization and reconstruction of low width algebraic branching programs. Comput. Complex. 28 (4) (2019)
Ankit Garg, Nikhil Gupta, Neeraj Kayal, Chandan Saha
Determinant equivalence test over finite fields and over $\mathbf{Q}$. Electron. Colloquium Comput. Complex. 26 (2019)
Neeraj Kayal, Chandan Saha
Guest Column: A Paradigm for Arithmetic Circuit Lower Bounds. SIGACT News 49 (1) (2018)
Neeraj Kayal, Chandan Saha, Sébastien Tavenas
On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree. Theory Comput. 14 (1) (2018)
Neeraj Kayal, Chandan Saha
Reconstruction of non-degenerate homogeneous depth three circuits. Electron. Colloquium Comput. Complex. 25 (2018)
Neeraj Kayal, Vineet Nair, Chandan Saha
Average-case linear matrix factorization and reconstruction of low width Algebraic Branching Programs. Electron. Colloquium Comput. Complex. 25 (2018)
Neeraj Kayal, Vineet Nair, Chandan Saha, Sébastien Tavenas
Reconstruction of Full Rank Algebraic Branching Programs. Computational Complexity Conference (2017)
Neeraj Kayal, Chandan Saha
Multi-k-ic Depth Three Circuit Lower Bound. Theory Comput. Syst. 61 (4) (2017)
Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan
An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas. SIAM J. Comput. 46 (1) (2017)
Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi
Unexpected power of low-depth arithmetic circuits. Commun. ACM 60 (6) (2017)
Neeraj Kayal, Vineet Nair, Chandan Saha, Sébastien Tavenas
Reconstruction of full rank Algebraic Branching Programs. Electron. Colloquium Comput. Complex. 24 (2017)
Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi
Arithmetic Circuits: A Chasm at Depth 3. SIAM J. Comput. 45 (3) (2016)
Neeraj Kayal, Vineet Nair, Chandan Saha
Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits. STACS (2016)
Neeraj Kayal, Chandan Saha
Lower Bounds for Depth-Three Arithmetic Circuits with small bottom fanin. Comput. Complex. 25 (2) (2016)
Neeraj Kayal, Chandan Saha, Sébastien Tavenas
On the size of homogeneous and of depth four formulas with low individual degree. STOC (2016)
Neeraj Kayal, Chandan Saha, Sébastien Tavenas
An almost Cubic Lower Bound for Depth Three Arithmetic Circuits. Electron. Colloquium Comput. Complex. 23 (2016)
Neeraj Kayal, Chandan Saha, Sébastien Tavenas
An Almost Cubic Lower Bound for Depth Three Arithmetic Circuits. ICALP (2016)
Neeraj Kayal, Chandan Saha, Sébastien Tavenas
On the size of homogeneous and of depth four formulas with low individual degree. Electron. Colloquium Comput. Complex. 22 (2015)
Neeraj Kayal, Chandan Saha
Lower Bounds for Depth Three Arithmetic Circuits with Small Bottom Fanin. Computational Complexity Conference (2015)
Neeraj Kayal, Chandan Saha
Lower Bounds for Sums of Products of Low arity Polynomials. Electron. Colloquium Comput. Complex. 22 (2015)
Neeraj Kayal, Vineet Nair, Chandan Saha
Separation between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits. Electron. Colloquium Comput. Complex. 22 (2015)
Neeraj Kayal, Chandan Saha
Multi-k-ic Depth Three Circuit Lower Bound. STACS (2015)
Neeraj Kayal, Chandan Saha
-ic depth three circuit lower bound. Electron. Colloquium Comput. Complex. 22 (2015)
Neeraj Kayal, Pascal Koiran, Timothée Pecatte, Chandan Saha
Lower Bounds for Sums of Powers of Low Degree Univariates. ICALP (1) (2015)
Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan
Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas. STOC (2014)
Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan
An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas. Electron. Colloquium Comput. Complex. 21 (2014)
Neeraj Kayal
Arithmetic Circuit Complexity (Tutorial). STACS (2014)
Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan
An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas. FOCS (2014)
Ankit Gupta, Neeraj Kayal, Youming Qiao
Random arithmetic formulas can be reconstructed efficiently. Comput. Complex. 23 (2) (2014)
Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi
A super-polynomial lower bound for regular arithmetic formulas. STOC (2014)
Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi
Approaching the Chasm at Depth Four. J. ACM 61 (6) (2014)
Neeraj Kayal, Chandan Saha
Lower Bounds for Depth Three Arithmetic Circuits with small bottom fanin. Electron. Colloquium Comput. Complex. 21 (2014)
Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi
Arithmetic Circuits: A Chasm at Depth Three. FOCS (2013)
Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi
Approaching the Chasm at Depth Four. Computational Complexity Conference (2013)
Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi
Arithmetic circuits: A chasm at depth three. Electron. Colloquium Comput. Complex. 20 (2013)
Ankit Gupta, Neeraj Kayal, Youming Qiao
Random Arithmetic Formulas Can Be Reconstructed Efficiently. Computational Complexity Conference (2013)
Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi
A super-polynomial lower bound for regular arithmetic formulas. Electron. Colloquium Comput. Complex. 20 (2013)
Neeraj Kayal
Affine projections of polynomials: extended abstract. STOC (2012)
Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi
An exponential lower bound for homogeneous depth four arithmetic circuits with bounded bottom fanin. Electron. Colloquium Comput. Complex. 19 (2012)
Neeraj Kayal, Chandan Saha
On the Sum of Square Roots of Polynomials and Related Problems. ACM Trans. Comput. Theory 4 (4) (2012)
Ankit Gupta, Neeraj Kayal, Satyanarayana V. Lokam
Reconstruction of depth-4 multilinear circuits with top fan-in 2. STOC (2012)
Ankit Gupta, Neeraj Kayal, Youming Qiao
Random Arithmetic Formulas can be Reconstructed Efficiently. Electron. Colloquium Comput. Complex. 19 (2012)
Neeraj Kayal
An exponential lower bound for the sum of powers of bounded degree polynomials. Electron. Colloquium Comput. Complex. 19 (2012)
Neeraj Kayal
Efficient algorithms for some special cases of the polynomial equivalence problem. SODA (2011)
Ankit Gupta, Neeraj Kayal, Satyanarayana V. Lokam
Reconstruction of Depth-4 Multilinear Circuits with Top fanin 2. Electron. Colloquium Comput. Complex. 18 (2011)
Neeraj Kayal, Chandan Saha
On the Sum of Square Roots of Polynomials and Related Problems. Computational Complexity Conference (2011)
Neeraj Kayal
Affine projections of polynomials. Electron. Colloquium Comput. Complex. 18 (2011)
Michael A. Forbes, Neeraj Kayal, Rajat Mittal, Chandan Saha
Square root Bound on the Least Power Non-residue using a Sylvester-Vandermonde Determinant CoRR (2011)
Xi Chen, Neeraj Kayal, Avi Wigderson
Partial Derivatives in Arithmetic Complexity and Beyond. Found. Trends Theor. Comput. Sci. 6 (1-2) (2011)
Ankit Gupta, Neeraj Kayal, Satyanarayana V. Lokam
Efficient Reconstruction of Random Multilinear Formulas. FOCS (2011)
Neeraj Kayal
Algorithms for Arithmetic Circuits. Electron. Colloquium Comput. Complex. 17 (2010)
Neeraj Kayal, Chandan Saha
On the Sum of Square Roots of Polynomials and related problems. Electron. Colloquium Comput. Complex. 17 (2010)
Neeraj Kayal, Shubhangi Saraf
Blackbox Polynomial Identity Testing for Depth 3 Circuits. Electron. Colloquium Comput. Complex. 16 (2009)
Neeraj Kayal
The Complexity of the Annihilating Polynomial. Computational Complexity Conference (2009)
Neeraj Kayal, Shubhangi Saraf
Blackbox Polynomial Identity Testing for Depth 3 Circuits. FOCS (2009)
Neeraj Kayal, Timur Nezhmetdinov
Factoring Groups Efficiently. ICALP (1) (2009)
Neeraj Kayal, Timur Nezhmetdinov
Factoring groups efficiently. Electron. Colloquium Comput. Complex. 15 (074) (2008)
Neeraj Kayal, Nitin Saxena
Polynomial Identity Testing for Depth 3 Circuits. Comput. Complex. 16 (2) (2007)
Neeraj Kayal, Nitin Saxena
Polynomial Identity Testing for Depth 3 Circuits. Computational Complexity Conference (2006)
Neeraj Kayal, Nitin Saxena
Complexity of Ring Morphism Problems. Comput. Complex. 15 (4) (2006)
Neeraj Kayal
Solvability of a System of Bivariate Polynomial Equations over a Finite Field. ICALP (2005)
Neeraj Kayal
Recognizing permutation functions in polynomial time. Electron. Colloquium Comput. Complex. (008) (2005)
Neeraj Kayal, Nitin Saxena
Polynomial Identity Testing for Depth 3 Circuits Electron. Colloquium Comput. Complex. (150) (2005)
Neeraj Kayal, Nitin Saxena
On the Ring Isomorphism and Automorphism Problems. Computational Complexity Conference (2005)
Neeraj Kayal, Nitin Saxena
On the Ring Isomorphism & Automorphism Problems Electron. Colloquium Comput. Complex. (109) (2004)