Helsinki Algorithms Seminar: "On Approximation of Rank of Symbolic Matrices" Gorav Jindal
Weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design
Map © OpenStreetMap. Some rights reserved.
Gorav Jindal
On Approximation of Rank of Symbolic Matrices
Abstract:
We consider the problem of computing the (commutative) rank of a given symbolic matrix. A symbolic matrix is an n x n matrix whose entries are (homogeneous) linear forms in variables x_1, x_2, ..., x_m over the given field F. This (commutative) rank is considered over the rational function field F(x_1, x_2, ..., x_m). This problem is fundamental, as it generalizes several computational problems from algebra and combinatorics. Finding an efficient deterministic algorithm for 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 a given symbolic matrix in deterministic polynomial time. It is known that the non-commutative rank is at most twice the (commutative) rank, one immediately gets a deterministic 1/2-approximation algorithm for the (commutative) rank.
It is a natural question whether this approximation ratio can be improved. In this work, we answer this question affirmatively. We present a deterministic polynomial-time approximation scheme (PTAS) for computing the (commutative) rank.
This is a joint work with Markus Bläser and Anurag Pandey and was published in 32nd Computational Complexity Conference (CCC 2017).
**
Helsinki Algorithms Seminar is a weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design, broadly interpreted to cover both theoretical ideas and algorithm engineering on concrete computing platforms. In most cases we have a presentation prepared for each meeting to communicate an idea, a recent result, work-in-progress, or demo, but this should not be at the expense of discussion and simply having fun with algorithms.
Our affiliations are with Aalto University and the University of Helsinki, and accordingly our activities alternate between the Otaniemi Campus of Aalto University and the Kumpula Campus of University of Helsinki, catalyzed by the Helsinki Institute for Information Technology HIIT, under the Algorithmic Data Analysis (ADA) programme.
Welcome!