default search action
Neeraj Kayal
Person information
- affiliation: Microsoft Research, Bangalore, India
- award (2006): Gödel Prize
- award (2006): Fulkerson Prize
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2024
- [c31]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: 25:1-25:19 - 2023
- [c30]Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, Bhargav Thankey:
Low-Depth Arithmetic Circuit Lower Bounds: Bypassing Set-Multilinearization. ICALP 2023: 12:1-12:20 - [i33]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 abs/2311.07284 (2023) - [i32]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. TR23 (2023) - 2022
- [c29]Vishwas Bhargava
, Ankit Garg, Neeraj Kayal, Chandan Saha:
Learning Generalized Depth Three Arithmetic Circuits in the Non-Degenerate Case. APPROX/RANDOM 2022: 21:1-21:22 - [i31]Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, Bhargav Thankey:
Low-depth arithmetic circuit lower bounds via shifted partials. CoRR abs/2211.07691 (2022) - [i30]Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, Bhargav Thankey:
Low-depth arithmetic circuit lower bounds via shifted partials. Electron. Colloquium Comput. Complex. TR22 (2022) - 2021
- [i29]Vishwas Bhargava, Ankit Garg, Neeraj Kayal, Chandan Saha:
Learning generalized depth-three arithmetic circuits in the non-degenerate case. Electron. Colloquium Comput. Complex. TR21 (2021) - 2020
- [j16]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): 2:1-2:27 (2020) - [c28]Ankit Garg, Neeraj Kayal, Chandan Saha:
Learning sums of powers of low-degree polynomials in the non-degenerate case. FOCS 2020: 889-899 - [i28]Ankit Garg, Neeraj Kayal, Chandan Saha:
Learning sums of powers of low-degree polynomials in the non-degenerate case. CoRR abs/2004.06898 (2020) - [i27]Ankit Garg, Neeraj Kayal, Chandan Saha:
Learning sums of powers of low-degree polynomials in the non-degenerate case. Electron. Colloquium Comput. Complex. TR20 (2020)
2010 – 2019
- 2019
- [j15]Neeraj Kayal, Vineet Nair, Chandan Saha:
Average-case linear matrix factorization and reconstruction of low width algebraic branching programs. Comput. Complex. 28(4): 749-828 (2019) - [j14]Neeraj Kayal, Vineet Nair, Chandan Saha, Sébastien Tavenas:
Reconstruction of Full Rank Algebraic Branching Programs. ACM Trans. Comput. Theory 11(1): 2:1-2:56 (2019) - [c27]Ankit Garg, Nikhil Gupta, Neeraj Kayal, Chandan Saha:
Determinant Equivalence Test over Finite Fields and over Q. ICALP 2019: 62:1-62:15 - [c26]Neeraj Kayal, Chandan Saha:
Reconstruction of non-degenerate homogeneous depth three circuits. STOC 2019: 413-424 - [i26]Ankit Garg, Nikhil Gupta, Neeraj Kayal, Chandan Saha:
Determinant equivalence test over finite fields and over ℚ. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [j13]Neeraj Kayal, Chandan Saha:
Guest Column: A Paradigm for Arithmetic Circuit Lower Bounds. SIGACT News 49(1): 55-65 (2018) - [j12]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): 1-46 (2018) - [i25]Neeraj Kayal, Vineet Nair, Chandan Saha:
Average-case linear matrix factorization and reconstruction of low width Algebraic Branching Programs. Electron. Colloquium Comput. Complex. TR18 (2018) - [i24]Neeraj Kayal, Chandan Saha:
Reconstruction of non-degenerate homogeneous depth three circuits. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [j11]Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi
Unexpected power of low-depth arithmetic circuits. Commun. ACM 60(6): 93-100 (2017) - [j10]Neeraj Kayal, Chandan Saha:
Multi-k-ic Depth Three Circuit Lower Bound. Theory Comput. Syst. 61(4): 1237-1251 (2017) - [j9]Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan
An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas. SIAM J. Comput. 46(1): 307-335 (2017) - [c25]Neeraj Kayal, Vineet Nair, Chandan Saha, Sébastien Tavenas:
Reconstruction of Full Rank Algebraic Branching Programs. CCC 2017: 21:1-21:61 - [i23]Neeraj Kayal, Vineet Nair, Chandan Saha, Sébastien Tavenas:
Reconstruction of full rank Algebraic Branching Programs. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [j8]Neeraj Kayal, Chandan Saha:
Lower Bounds for Depth-Three Arithmetic Circuits with small bottom fanin. Comput. Complex. 25(2): 419-454 (2016) - [j7]Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi
Arithmetic Circuits: A Chasm at Depth 3. SIAM J. Comput. 45(3): 1064-1079 (2016) - [c24]Neeraj Kayal, Chandan Saha, Sébastien Tavenas:
An Almost Cubic Lower Bound for Depth Three Arithmetic Circuits. ICALP 2016: 33:1-33:15 - [c23]Neeraj Kayal, Vineet Nair, Chandan Saha:
Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits. STACS 2016: 46:1-46:15 - [c22]Neeraj Kayal, Chandan Saha, Sébastien Tavenas:
On the size of homogeneous and of depth four formulas with low individual degree. STOC 2016: 626-632 - [i22]Neeraj Kayal, Chandan Saha, Sébastien Tavenas:
An almost Cubic Lower Bound for Depth Three Arithmetic Circuits. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [c21]Neeraj Kayal, Chandan Saha:
Lower Bounds for Depth Three Arithmetic Circuits with Small Bottom Fanin. CCC 2015: 158-208 - [c20]Neeraj Kayal, Pascal Koiran, Timothée Pecatte, Chandan Saha:
Lower Bounds for Sums of Powers of Low Degree Univariates. ICALP (1) 2015: 810-821 - [c19]Neeraj Kayal, Chandan Saha:
Multi-k-ic Depth Three Circuit Lower Bound. STACS 2015: 527-539 - [i21]Neeraj Kayal, Vineet Nair, Chandan Saha:
Separation between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits. Electron. Colloquium Comput. Complex. TR15 (2015) - [i20]Neeraj Kayal, Chandan Saha:
Multi-k-ic depth three circuit lower bound. Electron. Colloquium Comput. Complex. TR15 (2015) - [i19]Neeraj Kayal, Chandan Saha:
Lower Bounds for Sums of Products of Low arity Polynomials. Electron. Colloquium Comput. Complex. TR15 (2015) - [i18]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. TR15 (2015) - 2014
- [j6]Ankit Gupta, Neeraj Kayal, Youming Qiao
Random arithmetic formulas can be reconstructed efficiently. Comput. Complex. 23(2): 207-303 (2014) - [j5]Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi
Approaching the Chasm at Depth Four. J. ACM 61(6): 33:1-33:16 (2014) - [c18]Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan
An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas. FOCS 2014: 61-70 - [c17]Neeraj Kayal:
Arithmetic Circuit Complexity (Tutorial). STACS 2014: 28-28 - [c16]Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan
Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas. STOC 2014: 119-127 - [c15]Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi
A super-polynomial lower bound for regular arithmetic formulas. STOC 2014: 146-153 - [i17]Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan:
An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas. Electron. Colloquium Comput. Complex. TR14 (2014) - [i16]Neeraj Kayal, Chandan Saha:
Lower Bounds for Depth Three Arithmetic Circuits with small bottom fanin. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [c14]Ankit Gupta, Neeraj Kayal, Youming Qiao
Random Arithmetic Formulas Can Be Reconstructed Efficiently. CCC 2013: 1-9 - [c13]Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi
Approaching the Chasm at Depth Four. CCC 2013: 65-73 - [c12]Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi
Arithmetic Circuits: A Chasm at Depth Three. FOCS 2013: 578-587 - [i15]Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi:
Arithmetic circuits: A chasm at depth three. Electron. Colloquium Comput. Complex. TR13 (2013) - [i14]Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi:
A super-polynomial lower bound for regular arithmetic formulas. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [j4]Neeraj Kayal, Chandan Saha:
On the Sum of Square Roots of Polynomials and Related Problems. ACM Trans. Comput. Theory 4(4): 9:1-9:15 (2012) - [c11]Ankit Gupta, Neeraj Kayal, Satyanarayana V. Lokam:
Reconstruction of depth-4 multilinear circuits with top fan-in 2. STOC 2012: 625-642 - [c10]Neeraj Kayal:
Affine projections of polynomials: extended abstract. STOC 2012: 643-662 - [i13]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. TR12 (2012) - [i12]Ankit Gupta, Neeraj Kayal, Youming Qiao:
Random Arithmetic Formulas can be Reconstructed Efficiently. Electron. Colloquium Comput. Complex. TR12 (2012) - [i11]Neeraj Kayal:
An exponential lower bound for the sum of powers of bounded degree polynomials. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [j3]Xi Chen
Partial Derivatives in Arithmetic Complexity and Beyond. Found. Trends Theor. Comput. Sci. 6(1-2): 1-138 (2011) - [c9]Neeraj Kayal, Chandan Saha:
On the Sum of Square Roots of Polynomials and Related Problems. CCC 2011: 292-299 - [c8]Ankit Gupta, Neeraj Kayal, Satyanarayana V. Lokam:
Efficient Reconstruction of Random Multilinear Formulas. FOCS 2011: 778-787 - [c7]Neeraj Kayal:
Efficient algorithms for some special cases of the polynomial equivalence problem. SODA 2011: 1409-1421 - [i10]Michael Forbes, Neeraj Kayal, Rajat Mittal, Chandan Saha:
Square root Bound on the Least Power Non-residue using a Sylvester-Vandermonde Determinant. CoRR abs/1104.4557 (2011) - [i9]Ankit Gupta, Neeraj Kayal, Satyanarayana V. Lokam:
Reconstruction of Depth-4 Multilinear Circuits with Top fanin 2. Electron. Colloquium Comput. Complex. TR11 (2011) - [i8]Neeraj Kayal:
Affine projections of polynomials. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [i7]Neeraj Kayal:
Algorithms for Arithmetic Circuits. Electron. Colloquium Comput. Complex. TR10 (2010) - [i6]Neeraj Kayal, Chandan Saha:
On the Sum of Square Roots of Polynomials and related problems. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [c6]Neeraj Kayal:
The Complexity of the Annihilating Polynomial. CCC 2009: 184-193 - [c5]Neeraj Kayal, Shubhangi Saraf:
Blackbox Polynomial Identity Testing for Depth 3 Circuits. FOCS 2009: 198-207 - [c4]Neeraj Kayal, Timur Nezhmetdinov:
Factoring Groups Efficiently. ICALP (1) 2009: 585-596 - [i5]Neeraj Kayal, Shubhangi Saraf:
Blackbox Polynomial Identity Testing for Depth 3 Circuits. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [i4]Neeraj Kayal, Timur Nezhmetdinov:
Factoring groups efficiently. Electron. Colloquium Comput. Complex. TR08 (2008) - 2007
- [j2]Neeraj Kayal, Nitin Saxena
Polynomial Identity Testing for Depth 3 Circuits. Comput. Complex. 16(2): 115-138 (2007) - 2006
- [j1]Neeraj Kayal, Nitin Saxena
Complexity of Ring Morphism Problems. Comput. Complex. 15(4): 342-390 (2006) - [c3]Neeraj Kayal, Nitin Saxena
Polynomial Identity Testing for Depth 3 Circuits. CCC 2006: 9-17 - 2005
- [c2]Neeraj Kayal, Nitin Saxena
On the Ring Isomorphism and Automorphism Problems. CCC 2005: 2-12 - [c1]Neeraj Kayal:
Solvability of a System of Bivariate Polynomial Equations over a Finite Field. ICALP 2005: 551-562 - [i3]Neeraj Kayal:
Recognizing permutation functions in polynomial time. Electron. Colloquium Comput. Complex. TR05 (2005) - [i2]Neeraj Kayal, Nitin Saxena:
Polynomial Identity Testing for Depth 3 Circuits. Electron. Colloquium Comput. Complex. TR05 (2005) - 2004
- [i1]Neeraj Kayal, Nitin Saxena:
On the Ring Isomorphism & Automorphism Problems. Electron. Colloquium Comput. Complex. TR04 (2004)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-04-25 05:54 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: