All reports by Author Nutan Limaye:

__
TR24-079
| 20th April 2024
__

Tuomas Hakoniemi , Nutan Limaye, Iddo Tzameret#### Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers

__
TR24-021
| 29th January 2024
__

Prasad Chaugule, Nutan Limaye#### On the closures of monotone algebraic classes and variants of the determinant

__
TR23-191
| 2nd December 2023
__

Hervé Fournier, Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas#### On the Power of Homogeneous Algebraic Formulas

__
TR23-009
| 14th February 2023
__

Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan, Sébastien Tavenas#### Towards Optimal Depth-Reductions for Algebraic Formulas

__
TR22-139
| 15th October 2022
__

Radu Curticapean, Nutan Limaye, Srikanth Srinivasan#### On the VNP-hardness of Some Monomial Symmetric Polynomials

__
TR22-090
| 24th June 2022
__

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas#### On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials

__
TR21-094
| 6th July 2021
__

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas#### New Non-FPT Lower Bounds for Some Arithmetic Formulas

__
TR21-081
| 14th June 2021
__

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas#### Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits

Revisions: 1

__
TR20-152
| 7th October 2020
__

Prasad Chaugule, Nutan Limaye, Shourya Pandey#### Variants of the Determinant polynomial and VP-completeness

__
TR19-172
| 28th November 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!

__
TR19-133
| 2nd October 2019
__

Nutan Limaye, Srikanth Srinivasan, Utkarsh Tripathi#### More on $AC^0[\oplus]$ and Variants of the Majority Function

Revisions: 1

__
TR18-162
| 16th September 2018
__

Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, Srikanth Srinivasan#### A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates

__
TR18-157
| 10th September 2018
__

Nutan Limaye, Karteek Sreenivasiah, Srikanth Srinivasan, Utkarsh Tripathi, S Venkitesh#### The Coin Problem in Constant Depth: Sample Complexity and Parity gates

Revisions: 2

__
TR18-135
| 31st July 2018
__

Prasad Chaugule, Nutan Limaye, Aditya Varre#### Variants of Homomorphism Polynomials Complete for Algebraic Complexity Classes

Revisions: 1

__
TR18-062
| 7th April 2018
__

Suryajith Chillara, Christian Engels, Nutan Limaye, Srikanth Srinivasan#### A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits

__
TR17-156
| 15th October 2017
__

Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan#### Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications

__
TR17-077
| 30th April 2017
__

Guillaume Lagarde, Nutan Limaye, Srikanth Srinivasan#### Lower Bounds and PIT for Non-Commutative Arithmetic circuits with Restricted Parse Trees

__
TR17-019
| 8th February 2017
__

Andreas Krebs, Nutan Limaye, Michael Ludwig#### A Unified Method for Placing Problems in Polylogarithmic Depth

Revisions: 2

__
TR16-155
| 10th October 2016
__

Vaibhav Krishan, Nutan Limaye#### Isolation Lemma for Directed Reachability and NL vs. L

__
TR16-143
| 15th September 2016
__

Nikhil Balaji, Nutan Limaye, Srikanth Srinivasan#### An Almost Cubic Lower Bound for $\Sigma\Pi\Sigma$ Circuits Computing a Polynomial in VP

__
TR15-118
| 23rd July 2015
__

Hervé Fournier, Nutan Limaye, Meena Mahajan, Srikanth Srinivasan#### The shifted partial derivative complexity of Elementary Symmetric Polynomials

__
TR15-022
| 9th February 2015
__

Nutan Limaye, Guillaume Malod, Srikanth Srinivasan#### Lower bounds for non-commutative skew circuits

Revisions: 1

__
TR14-183
| 25th December 2014
__

Nikhil Balaji, Andreas Krebs, Nutan Limaye#### Skew Circuits of Small Width

__
TR14-180
| 22nd December 2014
__

Anna Gal, Jing-Tang Jang, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah#### Space-Efficient Approximations for Subset Sum

__
TR14-005
| 14th January 2014
__

Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan#### An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas

__
TR13-102
| 17th July 2013
__

Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah#### Small Depth Proof Systems

__
TR13-100
| 15th July 2013
__

Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan#### Lower bounds for depth $4$ formulas computing iterated matrix multiplication

__
TR12-186
| 27th December 2012
__

Andreas Krebs, Nutan Limaye#### DLOGTIME-Proof Systems

__
TR10-103
| 28th June 2010
__

Andreas Krebs, Nutan Limaye, Meena Mahajan#### Counting paths in VPA is complete for \#NC$^1$

__
TR10-094
| 17th May 2010
__

Ajesh Babu, Nutan Limaye, Girish Varma#### Streaming algorithms for some problems in log-space.

__
TR09-052
| 2nd May 2009
__

Fabian Wagner, Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf#### Planar Graph Isomorphism is in Log-space

__
TR07-087
| 11th July 2007
__

Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao#### Arithmetizing classes around NC^1 and L

__
TR06-009
| 10th January 2006
__

Nutan Limaye, Meena Mahajan, Jayalal Sarma#### Evaluating Monotone Circuits on Cylinders, Planes and Tori

Tuomas Hakoniemi , Nutan Limaye, Iddo Tzameret

Strong algebraic proof systems such as IPS (Ideal Proof System; Grochow-Pitassi JACM 2018) offer a general model for

deriving polynomials in an ideal and refuting unsatisfiable propositional formulas, subsuming most standard propositional proof systems. A major approach for lower bounding the size of IPS refutations is the Functional Lower Bound ...
more >>>

Prasad Chaugule, Nutan Limaye

In this paper we prove the following two results.

* We show that for any $C \in {mVF, mVP, mVNP}$, $C = \overline{C}$. Here, $mVF, mVP$, and $mVNP$ are monotone variants of $VF, VP$, and $VNP$, respectively. For an algebraic complexity class $C$, $\overline{C}$ denotes the closure of $C$. ...
more >>>

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

Proving explicit lower bounds on the size of algebraic formulas is a long-standing open problem in the area of algebraic complexity theory. Recent results in the area (e.g. a lower bound against constant-depth algebraic formulas due to Limaye, Srinivasan, and Tavenas (FOCS 2021)) have indicated a way forward for attacking ... more >>>

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

Classical results of Brent, Kuck and Maruyama (IEEE Trans. Computers 1973) and Brent (JACM 1974) show that any algebraic formula of size s can be converted to one of depth O(log s) with only a polynomial blow-up in size. In this paper, we consider a fine-grained version of this result ... more >>>

Radu Curticapean, Nutan Limaye, Srikanth Srinivasan

A polynomial $P\in F[x_1,\ldots,x_n]$ is said to be symmetric if it is invariant under any permutation of its input variables. The study of symmetric polynomials is a classical topic in mathematics, specifically in algebraic combinatorics and representation theory. More recently, they have been studied in several works in computer science, ... more >>>

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

We make progress on understanding a lower bound technique that was recently used by the authors to prove the first superpolynomial constant-depth circuit lower bounds against algebraic circuits.

More specifically, our previous work applied the well-known partial derivative method in a new setting, that of 'lopsided' set-multilinear polynomials. A ... more >>>

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

An Algebraic Formula for a polynomial $P\in F[x_1,\ldots,x_N]$ is an algebraic expression for $P(x_1,\ldots,x_N)$ using variables, field constants, additions and multiplications. Such formulas capture an algebraic analog of the Boolean complexity class $\mathrm{NC}^1.$ Proving lower bounds against this model is thus an important problem.

It is known that, to prove ... more >>>

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

An Algebraic Circuit for a polynomial $P\in F[x_1,\ldots,x_N]$ is a computational model for constructing the polynomial $P$ using only additions and multiplications. It is a \emph{syntactic} model of computation, as opposed to the Boolean Circuit model, and hence lower bounds for this model are widely expected to be easier to ... more >>>

Prasad Chaugule, Nutan Limaye, Shourya Pandey

The determinant is a canonical VBP-complete polynomial in the algebraic complexity setting. In this work, we introduce two variants of the determinant polynomial which we call $StackDet_n(X)$ and $CountDet_n(X)$ and show that they are VP and VNP complete respectively under $p$-projections. The definitions of the polynomials are inspired by a ... more >>>

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

Schur Polynomials are families of symmetric polynomials that have been

classically studied in Combinatorics and Algebra alike. They play a central

role in the study of Symmetric functions, in Representation theory [Sta99], in

Schubert calculus [LM10] as well as in Enumerative combinatorics [Gas96, Sta84,

Sta99]. In recent years, they have ...
more >>>

Nutan Limaye, Srikanth Srinivasan, Utkarsh Tripathi

In this paper we prove two results about $AC^0[\oplus]$ circuits.

We show that for $d(N) = o(\sqrt{\log N/\log \log N})$ and $N \leq s(N) \leq 2^{dN^{1/d^2}}$ there is an explicit family of functions $\{f_N:\{0,1\}^N\rightarrow \{0,1\}\}$ such that

$f_N$ has uniform $AC^0$ formulas of depth $d$ and size at ...
more >>>

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

We show that there is a randomized algorithm that, when given a small constant-depth Boolean circuit $C$ made up of gates that compute constant-degree Polynomial Threshold functions or PTFs (i.e., Boolean functions that compute signs of constant-degree polynomials), counts the number of satisfying assignments to $C$ in significantly better than ... more >>>

Nutan Limaye, Karteek Sreenivasiah, Srikanth Srinivasan, Utkarsh Tripathi, S Venkitesh

The $\delta$-Coin Problem is the computational problem of distinguishing between coins that are heads with probability $(1+\delta)/2$ or $(1-\delta)/2,$ where $\delta$ is a parameter that is going to $0$. We study the complexity of this problem in the model of constant-depth Boolean circuits and prove the following results.

1. Upper ... more >>>

Prasad Chaugule, Nutan Limaye, Aditya Varre

We present polynomial families complete for the well-studied algebraic complexity classes VF, VBP, VP, and VNP. The polynomial families are based on the homomorphism polynomials studied in the recent works of Durand et al. (2014) and Mahajan et al. (2016). We consider three different variants of graph homomorphisms, namely injective ... more >>>

Suryajith Chillara, Christian Engels, Nutan Limaye, Srikanth Srinivasan

We study the size blow-up that is necessary to convert an algebraic circuit of product-depth $\Delta+1$ to one of product-depth $\Delta$ in the multilinear setting.

We show that for every positive $\Delta = \Delta(n) = o(\log n/\log \log n),$ there is an explicit multilinear polynomial $P^{(\Delta)}$ on $n$ variables that ... more >>>

Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan

The complexity of Iterated Matrix Multiplication is a central theme in Computational Complexity theory, as the problem is closely related to the problem of separating various complexity classes within $\mathrm{P}$. In this paper, we study the algebraic formula complexity of multiplying $d$ many $2\times 2$ matrices, denoted $\mathrm{IMM}_{d}$, and show ... more >>>

Guillaume Lagarde, Nutan Limaye, Srikanth Srinivasan

We investigate the power of Non-commutative Arithmetic Circuits, which compute polynomials over the free non-commutative polynomial ring $\mathbb{F}\langle x_1,\dots,x_N \rangle$, where variables do not commute. We consider circuits that are restricted in the ways in which they can compute monomials: this can be seen as restricting the families of parse ... more >>>

Andreas Krebs, Nutan Limaye, Michael Ludwig

In this work we consider the term evaluation problem which involves, given a term over some algebra and a valid input to the term, computing the value of the term on that input. This is a classical problem studied under many names such as formula evaluation problem, formula value problem ... more >>>

Vaibhav Krishan, Nutan Limaye

In this work we study the problem of efficiently isolating witnesses for the complexity classes NL and LogCFL, which are two well-studied complexity classes contained in P. We prove that if there is a L/poly randomized procedure with success probability at least 2/3 for isolating an s-t path in a ... more >>>

Nikhil Balaji, Nutan Limaye, Srikanth Srinivasan

In this note, we prove that there is an explicit polynomial in VP such that any $\Sigma\Pi\Sigma$ arithmetic circuit computing it must have size at least $n^{3-o(1)}$. Up to $n^{o(1)}$ factors, this strengthens a recent result of Kayal, Saha and Tavenas (ICALP 2016) which gives a polynomial in VNP with ... more >>>

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

We continue the study of the shifted partial derivative measure, introduced by Kayal (ECCC 2012), which has been used to prove many strong depth-4 circuit lower bounds starting from the work of Kayal, and that of Gupta et al. (CCC 2013).

We show a strong lower bound on the dimension ... more >>>

Nutan Limaye, Guillaume Malod, Srikanth Srinivasan

Nisan (STOC 1991) exhibited a polynomial which is computable by linear sized non-commutative circuits but requires exponential sized non-commutative algebraic branching programs. Nisan's hard polynomial is in fact computable by linear sized skew circuits (skew circuits are circuits where every multiplication gate has the property that all but one of ... more >>>

Nikhil Balaji, Andreas Krebs, Nutan Limaye

A celebrated result of Barrington (1985) proved that polynomial size, width-5 branching programs (BP) are equivalent in power to a restricted form of branching programs -- polynomial sized width-5 permutation branching programs (PBP), which in turn capture all of NC1. On the other hand it is known that width-3 PBPs ... more >>>

Anna Gal, Jing-Tang Jang, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah

SUBSET SUM is a well known NP-complete problem:

given $t \in Z^{+}$ and a set $S$ of $m$ positive integers, output YES if and only if there is a subset $S^\prime \subseteq S$ such that the sum of all numbers in $S^\prime$ equals $t$. The problem and its search ...
more >>>

Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan

We show here a $2^{\Omega(\sqrt{d} \cdot \log N)}$ size lower bound for homogeneous depth four arithmetic formulas. That is, we give

an explicit family of polynomials of degree $d$ on $N$ variables (with $N = d^3$ in our case) with $0, 1$-coefficients such that

for any representation of ...
more >>>

Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah

A proof system for a language $L$ is a function $f$ such that Range$(f)$ is exactly $L$. In this paper, we look at proofsystems from a circuit complexity point of view and study proof systems that are computationally very restricted. The restriction we study is: they can be computed by ... more >>>

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

We study the arithmetic complexity of iterated matrix multiplication. We show that any multilinear homogeneous depth $4$ arithmetic formula computing the product of $d$ generic matrices of size $n \times n$, IMM$_{n,d}$, has size $n^{\Omega(\sqrt{d})}$ as long as $d \leq n^{1/10}$. This improves the result of Nisan and Wigderson (Computational ... more >>>

Andreas Krebs, Nutan Limaye

We define DLOGTIME proof systems, DLTPS, which generalize NC0 proof systems.

It is known that functions such as Exact-k and Majority do not have NC0 proof systems. Here, we give a DLTPS for Exact-k (and therefore for Majority) and also for other natural functions such as Reach and k-Clique. Though ...
more >>>

Andreas Krebs, Nutan Limaye, Meena Mahajan

We give a \#NC$^1$ upper bound for the problem of counting accepting paths in any fixed visibly pushdown automaton. Our algorithm involves a non-trivial adaptation of the arithmetic formula evaluation algorithm of Buss, Cook, Gupta, Ramachandran (BCGR: SICOMP 21(4), 1992). We also show that the problem is \#NC$^1$ hard. Our ... more >>>

Ajesh Babu, Nutan Limaye, Girish Varma

In this paper, we give streaming algorithms for some problems which are known to be in deterministic log-space, when the number of passes made on the input is unbounded. If the input data is massive,

the conventional deterministic log-space algorithms may not run efficiently. We study the complexity of the ...
more >>>

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

Graph Isomorphism is the prime example of a computational problem with a wide difference between the best known lower and upper bounds on its complexity. There is a significant gap between extant lower and upper bounds for planar graphs as well. We bridge the gap for this natural and ... more >>>

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

The parallel complexity class NC^1 has many equivalent models such as

polynomial size formulae and bounded width branching

programs. Caussinus et al. \cite{CMTV} considered arithmetizations of

two of these classes, #NC^1 and #BWBP. We further this study to

include arithmetization of other classes. In particular, we show that

counting paths ...
more >>>

Nutan Limaye, Meena Mahajan, Jayalal Sarma

We re-examine the complexity of evaluating monotone planar circuits

MPCVP, with special attention to circuits with cylindrical

embeddings. MPCVP is known to be in NC^3, and for the special

case of upward stratified circuits, it is known to be in

LogDCFL. We characterize cylindricality, which ...
more >>>