default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDNeeraj Kayal
Person information
- affiliation: Microsoft Research, Bangalore, India
- award (2006): Gödel Prize
- award (2006): Fulkerson Prize
SPARQL queries 
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
2020 – today
- 2026
[c32]Archish S, Ankit Garg, Kirankumar Shiragur, Neeraj Kayal:
Incorporating Token Importance in Multi-Vector Retrieval. AAAI 2026: 32860-32866- [i36]Archish S, Mihir Agarwal, Ankit Garg, Neeraj Kayal, Kirankumar Shiragur:
On Strengths and Limitations of Single-Vector Embeddings. CoRR abs/2603.29519 (2026) - 2025
- [i35]Kshitij Dubey, Benjamin Driscoll, Anjiang Wei, Neeraj Kayal, Rahul Sharma, Alex Aiken:
Equivalence Checking of ML GPU Kernels. CoRR abs/2511.12638 (2025) - [i34]Archish S, Ankit Garg, Kirankumar Shiragur, Neeraj Kayal:
Incorporating Token Importance in Multi-Vector Retrieval. CoRR abs/2511.16106 (2025) - 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: Article TR23-170 (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: Article TR22-151 (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: Article TR21-155 (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: Article TR20-045 (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: Article TR19-042 (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: Article TR18-029 (2018) - [i24]Neeraj Kayal, Chandan Saha:
Reconstruction of non-degenerate homogeneous depth three circuits. Electron. Colloquium Comput. Complex. TR18: Article TR18-191 (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: Article TR17-021 (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: Article TR16-006 (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: Article TR15-154 (2015) - [i20]Neeraj Kayal, Chandan Saha:
Multi-k-ic depth three circuit lower bound. Electron. Colloquium Comput. Complex. TR15: Article TR15-015 (2015) - [i19]Neeraj Kayal, Chandan Saha:
Lower Bounds for Sums of Products of Low arity Polynomials. Electron. Colloquium Comput. Complex. TR15: Article TR15-073 (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: Article TR15-181 (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: Article TR14-005 (2014) - [i16]Neeraj Kayal, Chandan Saha:
Lower Bounds for Depth Three Arithmetic Circuits with small bottom fanin. Electron. Colloquium Comput. Complex. TR14: Article TR14-089 (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: Article TR13-026 (2013) - [i14]Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi:
A super-polynomial lower bound for regular arithmetic formulas. Electron. Colloquium Comput. Complex. TR13: Article TR13-091 (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: Article TR12-098 (2012) - [i12]Ankit Gupta, Neeraj Kayal, Youming Qiao:
Random Arithmetic Formulas can be Reconstructed Efficiently. Electron. Colloquium Comput. Complex. TR12: Article TR12-033 (2012) - [i11]Neeraj Kayal:
An exponential lower bound for the sum of powers of bounded degree polynomials. Electron. Colloquium Comput. Complex. TR12: Article TR12-081 (2012) - 2011
- [j3]Xi Chen, Neeraj Kayal, Avi Wigderson:
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: Article TR11-153 (2011) - [i8]Neeraj Kayal:
Affine projections of polynomials. Electron. Colloquium Comput. Complex. TR11: Article TR11-061 (2011) - 2010
- [i7]Neeraj Kayal:
Algorithms for Arithmetic Circuits. Electron. Colloquium Comput. Complex. TR10: Article TR10-073 (2010) - [i6]Neeraj Kayal, Chandan Saha:
On the Sum of Square Roots of Polynomials and related problems. Electron. Colloquium Comput. Complex. TR10: Article TR10-189 (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: Article TR09-032 (2009) - 2008
- [i4]Neeraj Kayal, Timur Nezhmetdinov:
Factoring groups efficiently. Electron. Colloquium Comput. Complex. TR08: Article TR08-074 (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: Article TR05-008 (2005) - [i2]Neeraj Kayal, Nitin Saxena:
Polynomial Identity Testing for Depth 3 Circuits. Electron. Colloquium Comput. Complex. TR05: Article TR05-150 (2005) - 2004
- [i1]Neeraj Kayal, Nitin Saxena:
On the Ring Isomorphism & Automorphism Problems. Electron. Colloquium Comput. Complex. TR04: Article TR04-109 (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 2026-05-06 00:12 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, funded, and maintained by:
Schloss Dagstuhl - Leibniz Center for Informatics is a member of the Leibniz Association and is funded by the federal government of Germany and the states of Germany, especially Saarland and Rhineland‑Palatinate.
