All reports by Author Gorav Jindal:

__
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

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