Nutan Limaye

According to our database, Nutan Limaye authored at least 63 papers between 2006 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits.

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

Commun. ACM, February, 2024

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers.

Tuomas Hakoniemi, Nutan Limaye, Iddo Tzameret

Electron. Colloquium Comput. Complex., 2024

On the closures of monotone algebraic classes and variants of the determinant.

Prasad Chaugule, Nutan Limaye

Electron. Colloquium Comput. Complex., 2024

On the geometry of <i>k</i>-SAT solutions: what more can PPZ and Schöning's algorithms do?

Per Austrin, Ioana O. Bercea, Mayank Goswami, Nutan Limaye, Adarsh Srinivasan

CoRR, 2024

2023

Schur Polynomials Do Not Have Small Formulas If the Determinant does not.

Prasad Chaugule, Mrinal Kumar, Nutan Limaye, Chandra Kanta Mohapatra, Adrian She, Srikanth Srinivasan

Comput. Complex., June, 2023

Towards Optimal Depth-Reductions for Algebraic Formulas.

Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan, Sébastien Tavenas

Electron. Colloquium Comput. Complex., 2023

On the Power of Homogeneous Algebraic Formulas.

Hervé Fournier, Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

Electron. Colloquium Comput. Complex., 2023

2022

Guest Column: Lower Bounds Against Constant-Depth Algebraic Circuits.

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

SIGACT News, 2022

On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials.

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

Electron. Colloquium Comput. Complex., 2022

On the VNP-hardness of Some Monomial Symmetric Polynomials.

Radu Curticapean, Nutan Limaye, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2022

Set-multilinear and non-commutative formula lower bounds for iterated matrix multiplication.

Sébastien Tavenas, Nutan Limaye, Srikanth Srinivasan

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

2021

A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem.

Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan, Utkarsh Tripathi, S. Venkitesh

SIAM J. Comput., 2021

New Non-FPT Lower Bounds for Some Arithmetic Formulas.

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

Electron. Colloquium Comput. Complex., 2021

2020

Skew circuits of small width.

Nikhil Balaji, Andreas Krebs, Nutan Limaye

Theor. Comput. Sci., 2020

Variants of the Determinant polynomial and VP-completeness.

Prasad Chaugule, Nutan Limaye, Shourya Pandey

Electron. Colloquium Comput. Complex., 2020

2019

Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications.

Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan

SIAM J. Comput., 2019

More on $AC^0[\oplus]$ and Variants of the Majority Function.

Nutan Limaye, Srikanth Srinivasan, Utkarsh Tripathi

Electron. Colloquium Comput. Complex., 2019

Schur Polynomials do not have small formulas if the Determinant doesn't!

Prasad Chaugule, Mrinal Kumar, Nutan Limaye, Chandra Kanta Mohapatra, Adrian She, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2019

Lower Bounds and PIT for Non-commutative Arithmetic Circuits with Restricted Parse Trees.

Guillaume Lagarde, Nutan Limaye, Srikanth Srinivasan

Comput. Complex., 2019

A fixed-depth size-hierarchy theorem for AC⁰[⊕] via the coin problem.

Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan, Utkarsh Tripathi, S. Venkitesh

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

2018

The Coin Problem in Constant Depth: Sample Complexity and Parity gates.

Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan, Utkarsh Tripathi, S. Venkitesh

Electron. Colloquium Comput. Complex., 2018

A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits.

Suryajith Chillara, Christian Engels, Nutan Limaye, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2018

Variants of Homomorphism Polynomials Complete for Algebraic Complexity Classes.

Prasad Chaugule, Nutan Limaye, Aditya Varre

Electron. Colloquium Comput. Complex., 2018

A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates.

Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2018

A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas.

Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

2017

On the Maximum Rate of Networked Computation in a Capacitated Network.

Pooja Vyavahare, Nutan Limaye, Ajit A. Diwan, D. Manjunath

IEEE/ACM Trans. Netw., 2017

An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas.

Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan

SIAM J. Comput., 2017

A Unified Method for Placing Problems in Polylogarithmic Depth.

Andreas Krebs, Nutan Limaye, Michael Ludwig

Electron. Colloquium Comput. Complex., 2017

2016

Optimal Embedding of Functions for In-Network Computation: Complexity Analysis and Algorithms.

Pooja Vyavahare, Nutan Limaye, D. Manjunath

IEEE/ACM Trans. Netw., 2016

Isolation Lemma for Directed Reachability and NL vs. L.

Vaibhav Krishan, Nutan Limaye

Electron. Colloquium Comput. Complex., 2016

An Almost Cubic Lower Bound for ΣΠΣ Circuits Computing a Polynomial in VP.

Nikhil Balaji, Nutan Limaye, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2016

Cost Register Automata for Nested Words.

Andreas Krebs, Nutan Limaye, Michael Ludwig

Proceedings of the Computing and Combinatorics - 22nd International Conference, 2016

2015

Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication.

Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan

SIAM J. Comput., 2015

Lower bounds for non-commutative skew circuits.

Nutan Limaye, Guillaume Malod, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2015

The shifted partial derivative complexity of Elementary Symmetric Polynomials.

Hervé Fournier, Nutan Limaye, Meena Mahajan, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2015

On the Maximum Rate of Networked Computation in a Capacitated Network.

Pooja Vyavahare, Nutan Limaye, D. Manjunath

CoRR, 2015

Value Automata with Filters.

Michaël Cadilhac, Andreas Krebs, Nutan Limaye

CoRR, 2015

2014

Space-Efficient Approximations for Subset Sum.

Anna Gál, Jing-Tang Jang, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah

Electron. Colloquium Comput. Complex., 2014

Efficient Embedding of Functions in Weighted Communication Networks.

Pooja Vyavahare, Nutan Limaye, D. Manjunath

CoRR, 2014

Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas.

Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan

Proceedings of the Symposium on Theory of Computing, 2014

Information friction limits on computation.

Pooja Vyavahare, Majid Mahzoon, Pulkit Grover, Nutan Limaye, D. Manjunath

Proceedings of the 52nd Annual Allerton Conference on Communication, 2014

2013

Streaming algorithms for language recognition problems.

Ajesh Babu, Nutan Limaye, Jaikumar Radhakrishnan, Girish Varma

Theor. Comput. Sci., 2013

Small Depth Proof Systems.

Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah

Electron. Colloquium Comput. Complex., 2013

2012

DLOGTIME-Proof Systems.

Andreas Krebs, Nutan Limaye

Electron. Colloquium Comput. Complex., 2012

In-Network Estimation of Frequency Moments

Pooja Vyavahare, Nutan Limaye, D. Manjunath

CoRR, 2012

Counting Paths in VPA Is Complete for #NC 1.

Andreas Krebs, Nutan Limaye, Meena Mahajan

Algorithmica, 2012

The Complexity of Unary Subset Sum.

Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah

Proceedings of the Computing and Combinatorics - 18th Annual International Conference, 2012

2011

Streaming Algorithms for Recognizing Nearly Well-Parenthesized Expressions.

Andreas Krebs, Nutan Limaye, Srikanth Srinivasan

Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

2010

Planarity, Determinants, Permanents, and (Unique) Matchings.

Samir Datta, Raghav Kulkarni, Nutan Limaye, Meena Mahajan

ACM Trans. Comput. Theory, 2010

Arithmetizing Classes Around NC\textsf{NC}¹ and L\textsf{L}.

Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao

Theory Comput. Syst., 2010

Counting paths in VPA is complete for #NC¹.

Andreas Krebs, Nutan Limaye, Meena Mahajan

Electron. Colloquium Comput. Complex., 2010

Streaming algorithms for some problems in log-space.

Ajesh Babu, Nutan Limaye, Girish Varma

Electron. Colloquium Comput. Complex., 2010

Longest Paths in Planar DAGs in Unambiguous Log-Space.

Nutan Limaye, Meena Mahajan, Prajakta Nimbhorkar

Chic. J. Theor. Comput. Sci., 2010

2009

On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata.

Nutan Limaye, Meena Mahajan, Antoine Meyer

J. Autom. Lang. Comb., 2009

Planar Graph Isomorphism is in Log-space.

Fabian Wagner, Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf

Electron. Colloquium Comput. Complex., 2009

Upper Bounds for Monotone Planar Circuit Value and Variants.

Nutan Limaye, Meena Mahajan, Jayalal Sarma

Comput. Complex., 2009

Membership Testing: Removing Extra Stacks from Multi-stack Pushdown Automata.

Nutan Limaye, Meena Mahajan

Proceedings of the Language and Automata Theory and Applications, 2009

Longest Paths in Planar DAGs in Unambiguous Logspace.

Nutan Limaye, Meena Mahajan, Prajakta Nimbhorkar

Proceedings of the Theory of Computing 2009, 2009

2008

A Log-space Algorithm for Canonization of Planar Graphs

Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner

CoRR, 2008

3-connected Planar Graph Isomorphism is in Log-space.

Samir Datta, Nutan Limaye, Prajakta Nimbhorkar

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2008

2007

Arithmetizing classes around NC^1 and L.

Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao

Electron. Colloquium Comput. Complex., 2007

Arithmetizing Classes Around NC ¹ and L.

Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao

Proceedings of the STACS 2007, 2007

2006

Evaluating Monotone Circuits on Cylinders, Planes and Tori

Nutan Limaye, Meena Mahajan, Jayalal Sarma

Electron. Colloquium Comput. Complex., 2006