All reports by Author Anurag Pandey:

__
TR20-031
| 10th March 2020
__

Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh#### Algebraic Branching Programs, Border Complexity, and Tangent Spaces

__
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

Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh

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

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