N. Limaye

Most-cited papers

Lower bounds for depth 4 formulas computing iterated matrix multiplication
Hervé Fournier, N. Limaye, Guillaume Malod, Srikanth Srinivasan
2014SIAM journal on computing (Print)92 citations
Semantic Scholar
Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits
N. Limaye, Srikanth Srinivasan, Sébastien Tavenas
2022IEEE Annual Symposium on Foundations of Computer Science89 citations
Semantic Scholar
Planar Graph Isomorphism is in Log-Space
Samir Datta, N. Limaye, Prajakta Nimbhorkar, T. Thierauf +1 more
20092009 24th Annual IEEE Conference on Computational Complexity85 citations Open access
Semantic Scholar
An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas
N. Kayal, N. Limaye, Chandan Saha, Srikanth Srinivasan
2014IEEE Annual Symposium on Foundations of Computer Science70 citations
Semantic Scholar
Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications
S. Chillara, N. Limaye, Srikanth Srinivasan
2017Electron. Colloquium Comput. Complex.29 citations Open access
Semantic Scholar
Streaming algorithms for language recognition problems
Ajesh Babu, N. Limaye, Jaikumar Radhakrishnan, G. Varma
2011Theoretical Computer Science27 citations Open access
Semantic Scholar
Planarity, Determinants, Permanents, and (Unique) Matchings
Samir Datta, R. Kulkarni, N. Limaye, M. Mahajan
2007TOCT26 citations Open access
Semantic Scholar
Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas
N. Kayal, N. Limaye, Chandan Saha, Srikanth Srinivasan
2014Symposium on the Theory of Computing25 citations
Semantic Scholar
A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits
S. Chillara, C. Engels, N. Limaye, Srikanth Srinivasan
2018IEEE Annual Symposium on Foundations of Computer Science24 citations Open access
Semantic Scholar
Upper Bounds for Monotone Planar Circuit Value and Variants
N. Limaye, M. Mahajan, Jayalal Sarma
2009Computational Complexity24 citations
Semantic Scholar
Set-multilinear and non-commutative formula lower bounds for iterated matrix multiplication
Sébastien Tavenas, N. Limaye, Srikanth Srinivasan
2022Symposium on the Theory of Computing23 citations Open access
Semantic Scholar
A fixed-depth size-hierarchy theorem for AC0[⊕] via the coin problem
N. Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan, Utkarsh Tripathi +1 more
2018Symposium on the Theory of Computing20 citations
Semantic Scholar
Lower Bounds for Non-Commutative Skew Circuits
N. Limaye, Guillaume Malod, Srikanth Srinivasan
2016Theory of Computing20 citations Open access
Semantic Scholar
3-connected Planar Graph Isomorphism is in Log-space
Samir Datta, N. Limaye, Prajakta Nimbhorkar
2008Foundations of Software Technology and Theoretical Computer Science19 citations
Semantic Scholar
Lower Bounds and PIT for Non-commutative Arithmetic Circuits with Restricted Parse Trees
Guillaume Lagarde, N. Limaye, Srikanth Srinivasan
2018Computational Complexity18 citations Open access
Semantic Scholar
Evaluating Monotone Circuits on Cylinders, Planes and Tori
N. Limaye, M. Mahajan, Jayalal Sarma
2006Symposium on Theoretical Aspects of Computer Science18 citations
Semantic Scholar
Streaming Algorithms for Recognizing Nearly Well-Parenthesized Expressions
Andreas Krebs, N. Limaye, Srikanth Srinivasan
2011International Symposium on Mathematical Foundations of Computer Science17 citations Open access
Semantic Scholar
Longest Paths in Planar DAGs in Unambiguous Log-Space
N. Limaye, M. Mahajan, Prajakta Nimbhorkar
2008Chicago journal of theoretical computer science17 citations
Semantic Scholar
Optimal Embedding of Functions for In-Network Computation: Complexity Analysis and Algorithms
P. Vyavahare, N. Limaye, D. Manjunath
2014IEEE/ACM Transactions on Networking16 citations Open access
Semantic Scholar
Arithmetizing Classes Around NC 1 and L
N. Limaye, M. Mahajan, B. V. Raghavendra Rao
2007Symposium on Theoretical Aspects of Computer Science15 citations
Semantic Scholar
On the partial derivative method applied to lopsided set-multilinear polynomials
N. Limaye, Srikanth Srinivasan, Sébastien Tavenas
2022Electron. Colloquium Comput. Complex.11 citations
Semantic Scholar
Schur Polynomials Do Not Have Small Formulas If the Determinant does not
Prasad Chaugule, Mrinal Kumar, N. Limaye, C. K. Mohapatra +2 more
2019Computational Complexity11 citations
Semantic Scholar
Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
Tuomas Hakoniemi, N. Limaye, Iddo Tzameret
2024Electron. Colloquium Comput. Complex.10 citations Open access
Semantic Scholar
The Coin Problem in Constant Depth: Sample Complexity and Parity Gates
N. Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan, Utkarsh Tripathi +1 more
2018Electron. Colloquium Comput. Complex.9 citations
Semantic Scholar
A Log-space Algorithm for Canonization of Planar Graphs
Samir Datta, N. Limaye, Prajakta Nimbhorkar, T. Thierauf +1 more
2008arXiv.org9 citations
Semantic Scholar
Variants of Homomorphism Polynomials Complete for Algebraic Complexity Classes
Prasad Chaugule, N. Limaye, Aditya Varre
2019Electron. Colloquium Comput. Complex.8 citations Open access
Semantic Scholar
A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates
Swapnam Bajpai, Vaibhav Krishan, D. Kush, N. Limaye +1 more
2018Algorithmica8 citations Open access
Semantic Scholar
The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials
Hervé Fournier, N. Limaye, M. Mahajan, Srikanth Srinivasan
2015Theory of Computing8 citations Open access
Semantic Scholar
Streaming Algorithms for Some Problems in Log-Space
Ajesh Babu, N. Limaye, G. Varma
2010Theory and Applications of Models of Computation8 citations
Semantic Scholar
On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata
N. Limaye, M. Mahajan, A. Meyer
2008Computer Science Symposium in Russia8 citations Open access
Semantic Scholar
New Bounds for the Ideal Proof System in Positive Characteristic
Amik Raj Behera, N. Limaye, Varun Ramanathan, Srikanth Srinivasan
2025International Colloquium on Automata, Languages and Programming7 citations
Semantic Scholar
On the Power of Homogeneous Algebraic Formulas
Hervé Fournier, N. Limaye, Srikanth Srinivasan, Sébastien Tavenas
2024Electron. Colloquium Comput. Complex.7 citations Open access
Semantic Scholar
Algorithms for the Diverse-k-SAT Problem: The Geometry of Satisfying Assignments
Per Austrin, I. Bercea, Mayank Goswami, N. Limaye +1 more
2024International Colloquium on Automata, Languages and Programming7 citations
Semantic Scholar
A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas
S. Chillara, N. Limaye, Srikanth Srinivasan
2018International Colloquium on Automata, Languages and Programming6 citations
Semantic Scholar
Cost Register Automata for Nested Words
Andreas Krebs, N. Limaye, Michael Ludwig
2016International Computing and Combinatorics Conference6 citations
Semantic Scholar
Value Automata with Filters
M. Cadilhac, Andreas Krebs, N. Limaye
2015arXiv.org6 citations
Semantic Scholar
Arithmetizing Classes Around $\textsf{NC}$1 and $\textsf{L}$
N. Limaye, M. Mahajan, B. V. Raghavendra Rao
2010Theory of Computing Systems5 citations
Semantic Scholar
Counting Paths in VPA Is Complete for #NC1
Andreas Krebs, N. Limaye, M. Mahajan
2010Algorithmica5 citations Open access
Semantic Scholar
Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits
N. Limaye, Srikanth Srinivasan, Sébastien Tavenas
2024Communications of the ACM4 citations Open access
Semantic Scholar
Homogeneous ABP complexity of Elementary Symmetric Polynomials
N. Limaye, K. Mittal, M. Pareek
20194 citations
Semantic Scholar
A Unified Method for Placing Problems in Polylogarithmic Depth
Andreas Krebs, N. Limaye, Michael Ludwig
2017Foundations of Software Technology and Theoretical Computer Science4 citations
Semantic Scholar
Space-Efficient Approximations for Subset Sum
Anna Gál, Jing-Tang Jang, N. Limaye, M. Mahajan +1 more
2016ACM Transactions on Computation Theory4 citations
Semantic Scholar
An Almost Cubic Lower Bound for ΣΠΣ Circuits Computing a Polynomial in VP
N. Balaji, N. Limaye, Srikanth Srinivasan
2016Electron. Colloquium Comput. Complex.4 citations
Semantic Scholar
Small Depth Proof Systems
Andreas Krebs, N. Limaye, M. Mahajan, Karteek Sreenivasaiah
2013International Symposium on Mathematical Foundations of Computer Science4 citations Open access
Semantic Scholar
Using Preservation Theorems for Inexpressibility Results in First Order Logic
Abhisekh Sankaran, N. Limaye, Akshay Sundararaman, Supratik Chakraborty
20124 citations
Semantic Scholar
Towards Optimal Depth-Reductions for Algebraic Formulas
Hervé Fournier, N. Limaye, Guillaume Malod, Srikanth Srinivasan +1 more
2023Computational Complexity3 citations
Semantic Scholar
More on AC0[⊕] and Variants of the Majority Function
N. Limaye, Srikanth Srinivasan, Utkarsh Tripathi
20193 citations
Semantic Scholar
Information friction limits on computation
P. Vyavahare, Majid Mahzoon, Pulkit Grover, N. Limaye +1 more
2014Allerton Conference on Communication, Control, and Computing3 citations
Semantic Scholar
The Complexity of Unary Subset Sum
N. Limaye, M. Mahajan, Karteek Sreenivasaiah
2012International Computing and Combinatorics Conference3 citations
Semantic Scholar
Membership Testing: Removing Extra Stacks from Multi-stack Pushdown Automata
N. Limaye, M. Mahajan
2009Language and Automata Theory and Applications3 citations
Semantic Scholar