Nutan Limaye

ORCID

Publication Activity (10 Years)

Years Active: 2006-2024
Publications (10 Years): 65

Top Venues

Electron. Colloquium Comput. Complex.

CoRR

STOC

ACM Trans. Comput. Theory

Publications

Hervé Fournier, Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas
On the Power of Homogeneous Algebraic Formulas. STOC (2024)
Prasad Chaugule, Nutan Limaye
On the closures of monotone algebraic classes and variants of the determinant. Electron. Colloquium Comput. Complex. (2024)
Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas
Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits. Commun. ACM 67 (2) (2024)
Tuomas Hakoniemi, Nutan Limaye, Iddo Tzameret
Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers. STOC (2024)
Tuomas Hakoniemi, Nutan Limaye, Iddo Tzameret
Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers. Electron. Colloquium Comput. Complex. (2024)
Prasad Chaugule, Nutan Limaye
On The Closures of Monotone Algebraic Classes and Variants of the Determinant. Algorithmica 86 (7) (2024)
Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan, Sébastien Tavenas
Towards Optimal Depth-Reductions for Algebraic Formulas. CoRR (2023)
Prasad Chaugule, Mrinal Kumar, Nutan Limaye, Chandra Kanta Mohapatra, Adrian She, Srikanth Srinivasan
Schur Polynomials Do Not Have Small Formulas If the Determinant does not. Comput. Complex. 32 (1) (2023)
Hervé Fournier, Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas
On the Power of Homogeneous Algebraic Formulas. Electron. Colloquium Comput. Complex. (2023)
Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan, Sébastien Tavenas
Towards Optimal Depth-Reductions for Algebraic Formulas. Electron. Colloquium Comput. Complex. (2023)
Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan, Sébastien Tavenas
Towards Optimal Depth-Reductions for Algebraic Formulas. CCC (2023)
Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas
On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials. Electron. Colloquium Comput. Complex. (2022)
Radu Curticapean, Nutan Limaye, Srikanth Srinivasan
On the VNP-hardness of Some Monomial Symmetric Polynomials. Electron. Colloquium Comput. Complex. (2022)
Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas
Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits. FOCS (2022)
Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas
Guest Column: Lower Bounds Against Constant-Depth Algebraic Circuits. SIGACT News 53 (2) (2022)
Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, Srikanth Srinivasan
A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates. Algorithmica 84 (4) (2022)
Prasad Chaugule, Nutan Limaye
On the Closures of Monotone Algebraic Classes and Variants of the Determinant. LATIN (2022)
Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas
On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials. CCC (2022)
Radu Curticapean, Nutan Limaye, Srikanth Srinivasan
On the VNP-Hardness of Some Monomial Symmetric Polynomials. FSTTCS (2022)
Sébastien Tavenas, Nutan Limaye, Srikanth Srinivasan
Set-multilinear and non-commutative formula lower bounds for iterated matrix multiplication. STOC (2022)
Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner
Planar Graph Isomorphism Is in Log-Space. ACM Trans. Comput. Theory 14 (2) (2022)
Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas
New Non-FPT Lower Bounds for Some Arithmetic Formulas. Electron. Colloquium Comput. Complex. 28 (2021)
Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan, Utkarsh Tripathi, S. Venkitesh
A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem. SIAM J. Comput. 50 (4) (2021)
Prasad Chaugule, Nutan Limaye, Aditya Varre
Variants of Homomorphism Polynomials Complete for Algebraic Complexity Classes. ACM Trans. Comput. Theory 13 (4) (2021)
Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas
Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits. Electron. Colloquium Comput. Complex. 28 (2021)
Prasad Chaugule, Nutan Limaye, Shourya Pandey
Variants of the Determinant Polynomial and the VP-Completeness. CSR (2021)
Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas
Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits. FOCS (2021)
Prasad Chaugule, Mrinal Kumar, Nutan Limaye, Chandra Kanta Mohapatra, Adrian She, Srikanth Srinivasan
Schur Polynomials Do Not Have Small Formulas If the Determinant Doesn't. Computational Complexity Conference (2020)
Prasad Chaugule, Nutan Limaye, Shourya Pandey
Variants of the Determinant polynomial and VP-completeness. Electron. Colloquium Comput. Complex. 27 (2020)
Nikhil Balaji, Andreas Krebs, Nutan Limaye
Skew circuits of small width. Theor. Comput. Sci. 821 (2020)
Nutan Limaye, Srikanth Srinivasan, Utkarsh Tripathi
More on AC^0[oplus] and Variants of the Majority Function. FSTTCS (2019)
Guillaume Lagarde, Nutan Limaye, Srikanth Srinivasan
Lower Bounds and PIT for Non-commutative Arithmetic Circuits with Restricted Parse Trees. Comput. Complex. 28 (3) (2019)
Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan, Utkarsh Tripathi, S. Venkitesh
[⊕] via the coin problem. STOC (2019)
Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, Srikanth Srinivasan
A #SAT Algorithm for Small Constant-Depth Circuits with PTF Gates. ITCS (2019)
Prasad Chaugule, Mrinal Kumar, Nutan Limaye, Chandra Kanta Mohapatra, Adrian She, Srikanth Srinivasan
Schur Polynomials do not have small formulas if the Determinant doesn't! Electron. Colloquium Comput. Complex. 26 (2019)
Prasad Chaugule, Nutan Limaye, Aditya Varre
Variants of Homomorphism Polynomials Complete for Algebraic Complexity Classes. COCOON (2019)
Prasad Chaugule, Mrinal Kumar, Nutan Limaye, Chandra Kanta Mohapatra, Adrian She, Srikanth Srinivasan
Schur Polynomials do not have small formulas if the Determinant doesn't! CoRR (2019)
Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan
Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications. SIAM J. Comput. 48 (1) (2019)
Nutan Limaye, Srikanth Srinivasan, Utkarsh Tripathi
More on $AC^0[\oplus]$ and Variants of the Majority Function. Electron. Colloquium Comput. Complex. 26 (2019)
Suryajith Chillara, Christian Engels, Nutan Limaye, Srikanth Srinivasan
A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits. CoRR (2018)
Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan
A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas. ICALP (2018)
Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, Srikanth Srinivasan
A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates. CoRR (2018)
Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan, Utkarsh Tripathi, S. Venkitesh
The Coin Problem in Constant Depth: Sample Complexity and Parity Gates. CoRR (2018)
Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, Srikanth Srinivasan
A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates. Electron. Colloquium Comput. Complex. 25 (2018)
Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan, Utkarsh Tripathi, S. Venkitesh
The Coin Problem in Constant Depth: Sample Complexity and Parity gates. Electron. Colloquium Comput. Complex. 25 (2018)
Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan
Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications. STACS (2018)
Prasad Chaugule, Nutan Limaye, Aditya Varre
Variants of Homomorphism Polynomials Complete for Algebraic Complexity Classes. Electron. Colloquium Comput. Complex. 25 (2018)
Suryajith Chillara, Christian Engels, Nutan Limaye, Srikanth Srinivasan
A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits. FOCS (2018)
Suryajith Chillara, Christian Engels, Nutan Limaye, Srikanth Srinivasan
A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits. Electron. Colloquium Comput. Complex. 25 (2018)
Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan
Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications. CoRR (2017)
Andreas Krebs, Nutan Limaye, Michael Ludwig
A Unified Method for Placing Problems in Polylogarithmic Depth. FSTTCS (2017)
Andreas Krebs, Nutan Limaye, Michael Ludwig
A Unified Method for Placing Problems in Polylogarithmic Depth. Electron. Colloquium Comput. Complex. 24 (2017)
Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan
Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications. Electron. Colloquium Comput. Complex. 24 (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)
Hervé Fournier, Nutan Limaye, Meena Mahajan, Srikanth Srinivasan
The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials. Theory Comput. 13 (1) (2017)
Guillaume Lagarde, Nutan Limaye, Srikanth Srinivasan
Lower Bounds and PIT for Non-Commutative Arithmetic Circuits with Restricted Parse Trees. MFCS (2017)
Guillaume Lagarde, Nutan Limaye, Srikanth Srinivasan
Lower Bounds and PIT for Non-Commutative Arithmetic circuits with Restricted Parse Trees. Electron. Colloquium Comput. Complex. 24 (2017)
Pooja Vyavahare, Nutan Limaye, Ajit A. Diwan, D. Manjunath
On the Maximum Rate of Networked Computation in a Capacitated Network. IEEE/ACM Trans. Netw. 25 (4) (2017)
Vaibhav Krishan, Nutan Limaye
Isolation Lemma for Directed Reachability and NL vs. L. Electron. Colloquium Comput. Complex. 23 (2016)
Andreas Krebs, Nutan Limaye, Michael Ludwig
Cost Register Automata for Nested Words. COCOON (2016)
Anna Gál, Jing-Tang Jang, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah
Space-Efficient Approximations for Subset Sum. ACM Trans. Comput. Theory 8 (4) (2016)
Nikhil Balaji, Nutan Limaye, Srikanth Srinivasan
An Almost Cubic Lower Bound for ΣΠΣ Circuits Computing a Polynomial in VP. Electron. Colloquium Comput. Complex. 23 (2016)
Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah
Small Depth Proof Systems. ACM Trans. Comput. Theory 9 (1) (2016)
Pooja Vyavahare, Nutan Limaye, D. Manjunath
Optimal Embedding of Functions for In-Network Computation: Complexity Analysis and Algorithms. IEEE/ACM Trans. Netw. 24 (4) (2016)
Nutan Limaye, Guillaume Malod, Srikanth Srinivasan
Lower Bounds for Non-Commutative Skew Circuits. Theory Comput. 12 (1) (2016)
Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan
Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication. SIAM J. Comput. 44 (5) (2015)
Nutan Limaye, Guillaume Malod, Srikanth Srinivasan
Lower bounds for non-commutative skew circuits. Electron. Colloquium Comput. Complex. 22 (2015)
Hervé Fournier, Nutan Limaye, Meena Mahajan, Srikanth Srinivasan
The shifted partial derivative complexity of Elementary Symmetric Polynomials. Electron. Colloquium Comput. Complex. 22 (2015)
Nikhil Balaji, Andreas Krebs, Nutan Limaye
Skew Circuits of Small Width. COCOON (2015)
Michaël Cadilhac, Andreas Krebs, Nutan Limaye
Value Automata with Filters. CoRR (2015)
Hervé Fournier, Nutan Limaye, Meena Mahajan, Srikanth Srinivasan
The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials. MFCS (2) (2015)
Pooja Vyavahare, Nutan Limaye, D. Manjunath
On the Maximum Rate of Networked Computation in a Capacitated Network. CoRR (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)
Anna Gál, Jing-Tang Jang, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah
Space-Efficient Approximations for Subset Sum. Electron. Colloquium Comput. Complex. 21 (2014)
Pooja Vyavahare, Majid Mahzoon, Pulkit Grover, Nutan Limaye, D. Manjunath
Information friction limits on computation. Allerton (2014)
Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan
An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas. FOCS (2014)
Pooja Vyavahare, Nutan Limaye, D. Manjunath
Efficient Embedding of Functions in Weighted Communication Networks. CoRR (2014)
Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan
Lower bounds for depth 4 formulas computing iterated matrix multiplication. STOC (2014)
Nikhil Balaji, Andreas Krebs, Nutan Limaye
Skew Circuits of Small Width. Electron. Colloquium Comput. Complex. 21 (2014)
Andreas Krebs, Nutan Limaye
DLOGTIME Proof Systems. FSTTCS (2013)
Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah
Small Depth Proof Systems. Electron. Colloquium Comput. Complex. 20 (2013)
Ajesh Babu, Nutan Limaye, Jaikumar Radhakrishnan, Girish Varma
Streaming algorithms for language recognition problems. Theor. Comput. Sci. 494 (2013)
Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah
Small Depth Proof Systems. CoRR (2013)
Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah
Small Depth Proof Systems. MFCS (2013)
Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan
Lower bounds for depth 4 formulas computing iterated matrix multiplication. Electron. Colloquium Comput. Complex. 20 (2013)
Andreas Krebs, Nutan Limaye, Srikanth Srinivasan
Streaming algorithms for recognizing nearly well-parenthesized expressions CoRR (2012)
Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah
The Complexity of Unary Subset Sum. COCOON (2012)
Andreas Krebs, Nutan Limaye
DLOGTIME-Proof Systems. Electron. Colloquium Comput. Complex. 19 (2012)
Andreas Krebs, Nutan Limaye, Meena Mahajan
Counting Paths in VPA Is Complete for #NC 1. Algorithmica 64 (2) (2012)
Pooja Vyavahare, Nutan Limaye, D. Manjunath
In-Network Estimation of Frequency Moments CoRR (2012)
Andreas Krebs, Nutan Limaye, Srikanth Srinivasan
Streaming Algorithms for Recognizing Nearly Well-Parenthesized Expressions. MFCS (2011)
Ajesh Babu, Nutan Limaye, Jaikumar Radhakrishnan, Girish Varma
Streaming algorithms for language recognition problems CoRR (2011)
Samir Datta, Raghav Kulkarni, Nutan Limaye, Meena Mahajan
Planarity, Determinants, Permanents, and (Unique) Matchings. ACM Trans. Comput. Theory 1 (3) (2010)
Nutan Limaye, Meena Mahajan, Prajakta Nimbhorkar
Longest Paths in Planar DAGs in Unambiguous Log-Space. Chic. J. Theor. Comput. Sci. 2010 (2010)
Ajesh Babu, Nutan Limaye, Girish Varma
Streaming algorithms for some problems in log-space. Electron. Colloquium Comput. Complex. 17 (2010)
Andreas Krebs, Nutan Limaye, Meena Mahajan
. Electron. Colloquium Comput. Complex. 17 (2010)
Andreas Krebs, Nutan Limaye, Meena Mahajan
. COCOON (2010)
Ajesh Babu, Nutan Limaye, Girish Varma
Streaming Algorithms for Some Problems in Log-Space. TAMC (2010)
Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao
and L\textsf{L}. Theory Comput. Syst. 46 (3) (2010)

Nutan Limaye.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Nutan Limaye