Nutan Limaye

Available identifiers

zbMath Open limaye.nutanMaRDI QIDQ391076

List of research outcomes

Publication	Date of Publication	Type
Set-multilinear and non-commutative formula lower bounds for iterated matrix multiplication	2023-12-08	Paper
On the closures of monotone algebraic classes and variants of the determinant	2023-07-26	Paper
Schur polynomials do not have small formulas if the determinant does not	2023-07-10	Paper
https://portal.mardi4nfdi.de/entity/Q5875656	2023-02-03	Paper
https://portal.mardi4nfdi.de/entity/Q5092463	2022-07-21	Paper
https://portal.mardi4nfdi.de/entity/Q5090378	2022-07-18	Paper
Variants of Homomorphism Polynomials Complete for Algebraic Complexity Classes	2022-03-29	Paper
A \#SAT algorithm for small constant-depth circuits with PTF gates	2022-03-22	Paper
Variants of the determinant polynomial and the \textsf{VP}-completeness	2022-03-21	Paper
A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus$ via the Coin Problem]	2021-09-10	Paper
A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas	2021-07-28	Paper
https://portal.mardi4nfdi.de/entity/Q5136328	2020-11-25	Paper
Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications.	2020-08-05	Paper
https://portal.mardi4nfdi.de/entity/Q5111256	2020-05-26	Paper
Skew circuits of small width	2020-04-22	Paper
Variants of homomorphism polynomials complete for algebraic complexity classes	2020-02-24	Paper
A fixed-depth size-hierarchy theorem for AC 0 [⊕ via the coin problem]	2020-01-30	Paper
Small Depth Proof Systems	2019-12-06	Paper
Space-Efficient Approximations for Subset Sum	2019-12-06	Paper
Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees	2019-08-30	Paper
Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications	2019-01-14	Paper
https://portal.mardi4nfdi.de/entity/Q5368898	2017-10-11	Paper
An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas	2017-03-10	Paper
https://portal.mardi4nfdi.de/entity/Q2963912	2017-02-21	Paper
https://portal.mardi4nfdi.de/entity/Q2830870	2016-11-01	Paper
Cost Register Automata for Nested Words	2016-09-02	Paper
In-network estimation of frequency moments	2016-08-03	Paper
Skew Circuits of Small Width	2015-10-29	Paper
Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication	2015-10-08	Paper
Planarity, Determinants, Permanents, and (Unique) Matchings	2015-09-24	Paper
The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials	2015-09-16	Paper
Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas	2015-06-26	Paper
Lower bounds for depth 4 formulas computing iterated matrix multiplication	2015-06-26	Paper
https://portal.mardi4nfdi.de/entity/Q5414582	2014-05-06	Paper
Streaming algorithms for language recognition problems	2014-01-10	Paper
Small Depth Proof Systems	2013-09-20	Paper
Counting paths in VPA is complete for \(\#\mathrm{NC}^1\)	2012-11-21	Paper
3-connected Planar Graph Isomorphism is in Log-space	2012-10-19	Paper
The Complexity of Unary Subset Sum	2012-09-25	Paper
Streaming Algorithms for Recognizing Nearly Well-Parenthesized Expressions	2011-08-17	Paper
Upper bounds for monotone planar circuit value and variants	2011-02-18	Paper
https://portal.mardi4nfdi.de/entity/Q3589625	2010-09-20	Paper
Counting Paths in VPA Is Complete for #NC 1	2010-07-20	Paper
Streaming Algorithms for Some Problems in Log-Space	2010-06-17	Paper
Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}}	2010-05-05	Paper
Membership Testing: Removing Extra Stacks from Multi-stack Pushdown Automata	2009-04-02	Paper
On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata	2008-06-05	Paper
Planarity, Determinants, Permanents, and (Unique) Matchings	2008-06-03	Paper
Evaluating Monotone Circuits on Cylinders, Planes and Tori	2008-03-19	Paper
Arithmetizing Classes Around NC 1 and L	2007-09-03	Paper

Research outcomes over time

Doctoral students

No records found.

Known relations from the MaRDI Knowledge Graph

Property	Value
MaRDI profile type	MaRDI person profile
instance of	human

This page was built for person: Nutan Limaye