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

Given polynomials f,g,h\,\in \mathbb{F}[x_1,\ldots,x_n] such that f=g/h, where both g and h are computable by arithmetic circuits of size s, we show that f can be computed by a circuit of size \poly(s,\deg(h)). This solves a special case of division elimination for high-degree circuits (Kaltofen'87 \& WACT'16). The result ... more >>>

Algebraic natural proofs were recently introduced by Forbes, Shpilka and Volk (Proc. of the 49th Annual {ACM} {SIGACT} Symposium on Theory of Computing (STOC), pages {653--664}, 2017) and independently by Grochow, Kumar, Saks and Saraf~(CoRR, abs/1701.01717, 2017) as an attempt to transfer Razborov and Rudich's famous barrier result (J. Comput. ... more >>>

We consider the problem of commutative rank computation of a given matrix space, \mathcal{B}\subseteq\mathbb{F}^{n\times n}. The problem is fundamental, as it generalizes several computational problems from algebra and combinatorics. For instance, checking if the commutative rank of the space is n, subsumes problems such as testing perfect matching in graphs ... more >>>