All reports by Author Gorav Jindal:

__
TR22-157
| 16th November 2022
__

Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer, Gorav Jindal, Vladimir Lysikov#### Border complexity via elementary symmetric polynomials

Revisions: 1

__
TR21-072
| 23rd May 2021
__

Pranjal Dutta, Gorav Jindal, Anurag Pandey, Amit Sinhababu#### Arithmetic Circuit Complexity of Division and Truncation

__
TR18-064
| 3rd April 2018
__

Markus Bläser, Christian Ikenmeyer, Gorav Jindal, Vladimir Lysikov#### Generalized Matrix Completion and Algebraic Natural Proofs

__
TR16-145
| 16th September 2016
__

Markus Bläser, Gorav Jindal, Anurag Pandey#### Greedy Strikes Again: A Deterministic PTAS for Commutative Rank of Matrix Spaces

Revisions: 2

Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer, Gorav Jindal, Vladimir Lysikov

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

Pranjal Dutta, Gorav Jindal, Anurag Pandey, Amit Sinhababu

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

Markus Bläser, Christian Ikenmeyer, Gorav Jindal, Vladimir Lysikov

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

Markus Bläser, Gorav Jindal, Anurag Pandey

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