Nutan Limaye

According to our database, Nutan Limaye authored at least 67 papers between 2006 and 2025.

Collaborative distances:

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

2025

On Closure Properties of Read-Once Oblivious Algebraic Branching Programs.

Jules Armand, Prateek Dwivedi, Magnus Rahbek Dalgaard Hansen, Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

CoRR, September, 2025

#SAT-Algorithms for Classes of Threshold Circuits Based on Probabilistic Rank.

Nutan Limaye, Adarsh Srinivasan, Srikanth Srinivasan

Proceedings of the 50th International Symposium on Mathematical Foundations of Computer Science, 2025

New Bounds for the Ideal Proof System in Positive Characteristic.

Amik Raj Behera, Nutan Limaye, Varun Ramanathan, Srikanth Srinivasan

Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming, 2025

Algorithms for the Diverse-k-SAT Problem: The Geometry of Satisfying Assignments.

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

Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming, 2025

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

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

Tuomas Hakoniemi, Nutan Limaye, Iddo Tzameret

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

On the Power of Homogeneous Algebraic Formulas.

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

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 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

Proceedings of the 38th Computational Complexity Conference, 2023

2022

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

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

SIGACT News, 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

On the Closures of Monotone Algebraic Classes and Variants of the Determinant.

Prasad Chaugule, Nutan Limaye

Proceedings of the LATIN 2022: Theoretical Informatics, 2022

On the VNP-Hardness of Some Monomial Symmetric Polynomials.

Radu Curticapean, Nutan Limaye, Srikanth Srinivasan

Proceedings of the 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2022

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

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

Proceedings of the 37th Computational Complexity Conference, 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

Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits.

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Variants of the Determinant Polynomial and the VP-Completeness.

Prasad Chaugule, Nutan Limaye, Shourya Pandey

Proceedings of the Computer Science - Theory and Applications, 2021

2020

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

Proceedings of the 35th Computational Complexity Conference, 2020

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

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

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

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

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

Nutan Limaye, Srikanth Srinivasan, Utkarsh Tripathi

Proceedings of the 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2019

Variants of Homomorphism Polynomials Complete for Algebraic Complexity Classes.

Prasad Chaugule, Nutan Limaye, Aditya Varre

Proceedings of the Computing and Combinatorics - 25th International Conference, 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

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

Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan

Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, 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

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

Suryajith Chillara, Christian Engels, Nutan Limaye, Srikanth Srinivasan

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 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

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

Guillaume Lagarde, Nutan Limaye, Srikanth Srinivasan

Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

A Unified Method for Placing Problems in Polylogarithmic Depth.

Andreas Krebs, Nutan Limaye, Michael Ludwig

Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 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 non-commutative skew circuits.

Nutan Limaye, Guillaume Malod, 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

The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials.

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

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

Skew Circuits of Small Width.

Nikhil Balaji, Andreas Krebs, Nutan Limaye

Proceedings of the Computing and Combinatorics - 21st International Conference, 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

Lower bounds for depth 4 formulas computing iterated matrix multiplication.

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

Proceedings of the Symposium on Theory of Computing, 2014

An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas.

Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 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

Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

DLOGTIME Proof Systems.

Andreas Krebs, Nutan Limaye

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

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

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

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

Theory Comput. Syst., 2010

Longest Paths in Planar DAGs in Unambiguous Log-Space.

Nutan Limaye, Meena Mahajan, Prajakta Nimbhorkar

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

Streaming Algorithms for Some Problems in Log-Space.

Ajesh Babu, Nutan Limaye, Girish Varma

Proceedings of the Theory and Applications of Models of Computation, 7th Annual Conference, 2010

Counting Paths in VPA Is Complete for #NC¹.

Andreas Krebs, Nutan Limaye, Meena Mahajan

Proceedings of the Computing and Combinatorics, 16th Annual International Conference, 2010

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

Planar Graph Isomorphism is in Log-Space.

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

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 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

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

Nutan Limaye, Meena Mahajan, Antoine Meyer

Proceedings of the 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

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

Samir Datta, Raghav Kulkarni, Nutan Limaye, Meena Mahajan

Proceedings of the Computer Science, 2007

2006

Evaluating Monotone Circuits on Cylinders, Planes and Tori.

Nutan Limaye, Meena Mahajan, Jayalal Sarma

Proceedings of the STACS 2006, 2006