Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR16-145 | 3rd March 2017 04:51

Greedy Strikes Again: A Deterministic PTAS for Commutative Rank of Matrix Spaces

RSS-Feed




Revision #2
Authors: Markus Bläser, Gorav Jindal, Anurag Pandey
Accepted on: 3rd March 2017 04:51
Downloads: 765
Keywords: 


Abstract:

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 and identity testing of algebraic branching programs. An efficient deterministic computation of the commutative rank is a major open problem, although there is a simple and efficient randomized algorithm for it. Recently, there has been a series of results on computing the non-commutative rank of matrix spaces in deterministic polynomial time. Since the non-commutative rank of any matrix space is at most twice the commutative rank, one immediately gets a deterministic $\frac{1}{2}$-approximation algorithm for the computation of the commutative rank. This leads to a natural question of whether this approximation ratio can be improved. In this paper, we answer this question affirmatively.

We present a deterministic $\textrm{PTAS}$ for computing the commutative rank of a given matrix space. More specifically, given a matrix space $\mathcal{B}\subseteq\mathbb{F}^{n\times n}$ and a rational number $\epsilon > 0$, we give an algorithm, that runs in time $O(n^{4+\frac{3}{\epsilon}})$ and computes a matrix $A\in\mathcal{B}$ such that the rank of $A$ is at least $(1-\epsilon)$ times the commutative rank of $\mathcal{B}$. The algorithm is the natural greedy algorithm. It always takes the first set of $k$ matrices that will increase the rank of the matrix constructed so far until it does not find any improvement, where the size of the set $k$ depends on $\epsilon$.



Changes to previous version:

Fixed the proof of Lemma 19 (now Lemma 7) and moved some proofs to the appendix.


Revision #1 to TR16-145 | 23rd September 2016 19:53

Greedy Strikes Again: A Deterministic PTAS for Commutative Rank of Matrix Spaces





Revision #1
Authors: Markus Bläser, Gorav Jindal, Anurag Pandey
Accepted on: 23rd September 2016 19:53
Downloads: 1238
Keywords: 


Abstract:

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 and identity testing of algebraic branching programs. An efficient deterministic computation of the commutative rank is a major open problem, although there is a simple and efficient randomized algorithm for it. Recently, there has been a series of results on computing the non-commutative rank of matrix spaces in deterministic polynomial time. Since the non-commutative rank of any matrix space is at most twice the commutative rank, one immediately gets a deterministic $\frac{1}{2}$-approximation algorithm for the computation of the commutative rank. This leads to a natural question of whether this approximation ratio can be improved. In this paper, we answer this question affirmatively.

We present a deterministic $\textrm{PTAS}$ for computing the commutative rank of a given matrix space. More specifically, given a matrix space $\mathcal{B}\subseteq\mathbb{F}^{n\times n}$ and a rational number $\epsilon > 0$, we give an algorithm, that runs in time $O(n^{4+\frac{3}{\epsilon}})$ and computes a matrix $A\in\mathcal{B}$ such that the rank of $A$ is at least $(1-\epsilon)$ times the commutative rank of $\mathcal{B}$. The algorithm is the natural greedy algorithm. It always takes the first set of $k$ matrices that will increase the rank of the matrix constructed so far until it does not find any improvement, where the size of the set $k$ depends on $\epsilon$.



Changes to previous version:

As pointed out by Ankit Garg and Rafael Oliveira, there were some inaccuracies in the previous version. We fix those inaccuracies in this revision.


Paper:

TR16-145 | 16th September 2016 17:10

Greedy Strikes Again: A Deterministic PTAS for Commutative Rank of Matrix Spaces





TR16-145
Authors: Markus Bläser, Gorav Jindal, Anurag Pandey
Publication: 16th September 2016 21:23
Downloads: 1012
Keywords: 


Abstract:

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 and identity testing of algebraic branching programs. An efficient deterministic computation of the commutative rank is a major open problem, although there is a simple and efficient randomized algorithm for it. Recently, there has been a series of results on computing the non-commutative rank of matrix spaces in deterministic polynomial time. Since the non-commutative rank of any matrix space is at most twice the commutative rank, one immediately gets a deterministic $\frac{1}{2}$-approximation algorithm for the computation of the commutative rank. This leads to a natural question of whether this approximation ratio can be improved. In this paper, we answer this question affirmatively.

We present a deterministic $\textrm{PTAS}$ for computing the commutative rank of a given matrix space. More specifically, given a matrix space $\mathcal{B}\subseteq\mathbb{F}^{n\times n}$ and a rational number $\epsilon > 0$, we give an algorithm, that runs in time $O(n^{4+\frac{3}{\epsilon}})$ and computes a matrix $A\in\mathcal{B}$ such that the rank of $A$ is at least $(1-\epsilon)$ times the commutative rank of $\mathcal{B}$. The algorithm is the natural greedy algorithm. It always takes the first set of $k$ matrices that will increase the rank of the matrix constructed so far until it does not find any improvement, where the size of the set $k$ depends on $\epsilon$.



ISSN 1433-8092 | Imprint