Search Results

Documents authored by Blaeser, Markus

Document
DOI: 10.4230/LIPIcs.CCC.2017.33
Greedy Strikes Again: A Deterministic PTAS for Commutative Rank of Matrix Spaces

Authors: Markus Blaeser, Gorav Jindal, and Anurag Pandey

Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)

Abstract
We consider the problem of commutative rank computation of a given matrix space. A matrix space is a (linear) subspace of the (linear) space of n x n matrices over a given field. 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 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 Polynomial-time approximation scheme (PTAS) for computing the commutative rank of a given matrix space B. More specifically, given a matrix space and a rational number e > 0, we give an algorithm, that runs in time O(n^(4 + 3/e)) and computes a matrix A in the given matrix space B such that the rank of A is at least (1-e) times the commutative rank of 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 e.
Cite as

Markus Blaeser, Gorav Jindal, and Anurag Pandey. Greedy Strikes Again: A Deterministic PTAS for Commutative Rank of Matrix Spaces. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{blaeser_et_al:LIPIcs.CCC.2017.33,
  author =	{Blaeser, Markus and Jindal, Gorav and Pandey, Anurag},
  title =	{{Greedy Strikes Again: A Deterministic PTAS for Commutative Rank of Matrix Spaces}},
  booktitle =	{32nd Computational Complexity Conference (CCC 2017)},
  pages =	{33:1--33:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-040-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{79},
  editor =	{O'Donnell, Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.33},
  URN =		{urn:nbn:de:0030-drops-75194},
  doi =		{10.4230/LIPIcs.CCC.2017.33},
  annote =	{Keywords: Commutative Rank, Matrix Spaces, PTAS, Wong sequences}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.555
Randomness Efficient Testing of Sparse Black Box Identities of Unbounded Degree over the Reals

Authors: Markus Blaeser and Christian Engels

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
We construct a hitting set generator for sparse multivariate polynomials over the reals. The seed length of our generator is O(log^2 (mn/epsilon)) where m is the number of monomials, n is number of variables, and 1 - epsilon is the hitting probability. The generator can be evaluated in time polynomial in log m, n, and log 1/epsilon. This is the first hitting set generator whose seed length is independent of the degree of the polynomial. The seed length of the best generator so far by Klivans and Spielman [STOC 2001] depends logarithmically on the degree. From this, we get a randomized algorithm for testing sparse black box polynomial identities over the reals using O(log^2 (mn/epsilon)) random bits with running time polynomial in log m, n, and log(1/epsilon). We also design a deterministic test with running time ~O(m^3 n^3). Here, the ~O-notation suppresses polylogarithmic factors. The previously best deterministic test by Lipton and Vishnoi [SODA 2003] has a running time that depends polynomially on log delta, where $delta$ is the degree of the black box polynomial.
Cite as

Markus Blaeser and Christian Engels. Randomness Efficient Testing of Sparse Black Box Identities of Unbounded Degree over the Reals. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 555-566, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{blaeser_et_al:LIPIcs.STACS.2011.555,
  author =	{Blaeser, Markus and Engels, Christian},
  title =	{{Randomness Efficient Testing of Sparse Black Box Identities of Unbounded Degree over the Reals}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{555--566},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.555},
  URN =		{urn:nbn:de:0030-drops-30433},
  doi =		{10.4230/LIPIcs.STACS.2011.555},
  annote =	{Keywords: Descartes’ rule of signs, polynomial identity testing, sparse polynomials, black box testing}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact