We prove \Omega (n^2) complexity \emph{lower bound} for the
general model of \emph{randomized computation trees} solving
the \emph{Knapsack Problem}, and more generally \emph{Restricted
Integer Programming}. This is the \emph{first nontrivial} lower
bound proven for this model of computation. The method of the ... more >>>

In 1979 Valiant showed that the complexity class VP_e of families with polynomially bounded formula size is contained in the class VP_s of families that have algebraic branching programs (ABPs) of polynomially bounded size. Motivated by the problem of separating these classes we study the topological closure VP_e-bar, i.e. the ... more >>>

We show that over the field of complex numbers, every homogeneous polynomial of degree d can be approximated (in the border complexity sense) by a depth-3 arithmetic circuit of top fan-in at most d+1. This is quite surprising since there exist homogeneous polynomials P on n variables of degree 2, ... more >>>

A hitting-set generator (HSG) is a polynomial map Gen:\mathbb{F}^k \to \mathbb{F}^n such that for all n-variate polynomials Q of small enough circuit size and degree, if Q is non-zero, then Q\circ Gen is non-zero. In this paper, we give a new construction of such a HSG assuming that we have ... more >>>

Nisan showed in 1991 that the width of a smallest noncommutative single-(source,sink) algebraic branching program (ABP) to compute a noncommutative polynomial is given by the ranks of specific matrices. This means that the set of noncommutative polynomials with ABP width complexity at most k is Zariski-closed, an important property in ... more >>>

In (ToCT’20) Kumar surprisingly proved that every polynomial can be approximated as a sum of a constant and a product of linear polynomials. In this work, we prove the converse of Kumar's result which ramifies in a surprising new formulation of Waring rank and border Waring rank. From this conclusion, ... more >>>

VBP is the class of polynomial families that can be computed by the determinant of a symbolic matrix of the form A_0 + \sum_{i=1}^n A_ix_i where the size of each A_i is polynomial in the number of variables (equivalently, computable by polynomial-sized algebraic branching programs (ABP)). A major open problem ... more >>>

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 >>>