DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2024.63

Fractional Linear Matroid Matching Is in Quasi-NC

Authors: Rohit Gurjar, Taihei Oki, and Roshan Raj

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract

The matching and linear matroid intersection problems are solvable in quasi-NC, meaning that there exist deterministic algorithms that run in polylogarithmic time and use quasi-polynomially many parallel processors. However, such a parallel algorithm is unknown for linear matroid matching, which generalizes both of these problems. In this work, we propose a quasi-NC algorithm for fractional linear matroid matching, which is a relaxation of linear matroid matching and commonly generalizes fractional matching and linear matroid intersection. Our algorithm builds upon the connection of fractional matroid matching to non-commutative Edmonds' problem recently revealed by Oki and Soma (2023). As a corollary, we also solve black-box non-commutative Edmonds' problem with rank-two skew-symmetric coefficients.

Cite as

Rohit Gurjar, Taihei Oki, and Roshan Raj. Fractional Linear Matroid Matching Is in Quasi-NC. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 63:1-63:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gurjar_et_al:LIPIcs.ESA.2024.63,
  author =	{Gurjar, Rohit and Oki, Taihei and Raj, Roshan},
  title =	{{Fractional Linear Matroid Matching Is in Quasi-NC}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{63:1--63:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.63},
  URN =		{urn:nbn:de:0030-drops-211344},
  doi =		{10.4230/LIPIcs.ESA.2024.63},
  annote =	{Keywords: parallel algorithms, hitting set, non-commutative rank, Brascamp-Lieb polytope, algebraic algorithms}
}

Document

DOI: 10.4230/LIPIcs.CCC.2023.2

Border Complexity of Symbolic Determinant Under Rank One Restriction

Authors: Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, and Roshan Raj

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)

Abstract

VBP is the class of polynomial families that can be computed by the determinant of a symbolic matrix of the form A_0 + ∑_{i=1}^n A_i x_i where the size of each A_i is polynomial in the number of variables (equivalently, computable by polynomial-sized algebraic branching programs (ABP)). A major open problem in geometric complexity theory (GCT) is to determine whether VBP is closed under approximation i.e. whether VBP = VBP^ ̅. The power of approximation is well understood for some restricted models of computation, e.g. the class of depth-two circuits, read-once oblivious ABPs (ROABP), monotone ABPs, depth-three circuits of bounded top fan-in, and width-two ABPs. The former three classes are known to be closed under approximation [Markus Bläser et al., 2020], whereas the approximative closure of the last one captures the entire class of polynomial families computable by polynomial-sized formulas [Bringmann et al., 2017]. In this work, we consider the subclass of VBP computed by the determinant of a symbolic matrix of the form A_0 + ∑_{i=1}^n A_i x_i where for each 1 ≤ i ≤ n, A_i is of rank one. This class has been studied extensively [Edmonds, 1968; Jack Edmonds, 1979; Murota, 1993] and efficient identity testing algorithms are known for it [Lovász, 1989; Rohit Gurjar and Thomas Thierauf, 2020]. We show that this class is closed under approximation. In the language of algebraic geometry, we show that the set obtained by taking coordinatewise products of pairs of points from (the Plücker embedding of) a Grassmannian variety is closed.

Cite as

Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, and Roshan Raj. Border Complexity of Symbolic Determinant Under Rank One Restriction. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 2:1-2:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chatterjee_et_al:LIPIcs.CCC.2023.2,
  author =	{Chatterjee, Abhranil and Ghosh, Sumanta and Gurjar, Rohit and Raj, Roshan},
  title =	{{Border Complexity of Symbolic Determinant Under Rank One Restriction}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{2:1--2:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.2},
  URN =		{urn:nbn:de:0030-drops-182721},
  doi =		{10.4230/LIPIcs.CCC.2023.2},
  annote =	{Keywords: Border Complexity, Symbolic Determinant, Valuated Matroid}
}

Search Results

Documents authored by Raj, Roshan

Fractional Linear Matroid Matching Is in Quasi-NC

Abstract

Cite as

Border Complexity of Symbolic Determinant Under Rank One Restriction

Abstract

Cite as

Thanks for your feedback!

Could not send message