max planck institut

informatik

informatik

<< Previous Entry | Next Entry >> | New Event Entry | Edit this Entry | Login to DB (to update, delete) |

Title: | On Rank of Matrix Spaces |
---|---|

Speaker: | Gorav Jindal |

coming from: | Max-Planck-Institut für Informatik - D1 |

Speakers Bio: | |

Event Type: | AG1 Mittagsseminar (own work) |

Visibility: | D1 We use this to send out email in the morning. |

Level: | AG Audience |

Language: | English |

Date: | Thursday, 24 November 2016 |
---|---|

Time: | 13:00 |

Duration: | 45 Minutes |

Location: | Saarbrücken |

Building: | E1 4 |

Room: | 024 |

We consider the problem of commutative rank computation of a given matrix space, $\mathcal{B}\subseteq\mathbb{F}^{n\times n}$. The roblem 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 work, 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\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$. |

Name(s): | Gorav Jindal |
---|---|

Phone: | 015780883476 |

EMail: | --email address not disclosed on the web |

Video Broadcast: | No | To Location: |
---|

Keywords: | Matrix Spaces, Commutative Rank, PTAS. |
---|---|

Note: | |

Attachments, File(s): |

Created: | Gorav Jindal, 11/01/2016 07:46 PM | Last modified: | Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM |

- Gorav Jindal, 11/01/2016 07:46 PM
- Gorav Jindal, 11/01/2016 07:46 PM -- Created document.