Search Results

Documents authored by Oki, Taihei

Artifact
Software
DOI: 10.4230/artifacts.23553
Code for finding a non-SIBO matroid

Authors: Dániel Garamvölgyi, Ryuhei Mizutani, Taihei Oki, Tamás Schwarcz, and Yutaro Yamaguchi

Abstract
Cite as

Dániel Garamvölgyi, Ryuhei Mizutani, Taihei Oki, Tamás Schwarcz, Yutaro Yamaguchi. Code for finding a non-SIBO matroid (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-23553,
   title = {{Code for finding a non-SIBO matroid}}, 
   author = {Garamv\"{o}lgyi, D\'{a}niel and Mizutani, Ryuhei and Oki, Taihei and Schwarcz, Tam\'{a}s and Yamaguchi, Yutaro},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:ce3aedc8d6702824b0aaf570f3b345e2e24776c1;origin=https://github.com/taiheioki/sibo;visit=swh:1:snp:b12612e562c84d3ca5eb46a9baf151c8e2e2d3a5;anchor=swh:1:rev:79cbfd0a9fbdac083ee3d99fcf40ea4efd878bf8}{\texttt{swh:1:dir:ce3aedc8d6702824b0aaf570f3b345e2e24776c1}} (visited on 2025-06-30)},
   url = {https://github.com/taiheioki/sibo},
   doi = {10.4230/artifacts.23553},
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.85
Towards the Proximity Conjecture on Group-Labeled Matroids

Authors: Dániel Garamvölgyi, Ryuhei Mizutani, Taihei Oki, Tamás Schwarcz, and Yutaro Yamaguchi

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Consider a matroid M whose ground set is equipped with a labeling to an abelian group. A basis of M is called F-avoiding if the sum of the labels of its elements is not in a forbidden label set F. Hörsch, Imolay, Mizutani, Oki, and Schwarcz (2024) conjectured that if an F-avoiding basis exists, then any basis can be transformed into an F-avoiding basis by exchanging at most |F| elements. This proximity conjecture is known to hold for certain specific groups; in the case where |F| ≤ 2; or when the matroid is subsequence-interchangeably base orderable (SIBO), which is a weakening of the so-called strongly base orderable (SBO) property. In this paper, we settle the proximity conjecture for sparse paving matroids or in the case where |F| ≤ 4. Related to the latter result, we present the first known example of a non-SIBO matroid. We further address the setting of multiple group-label constraints, showing proximity results for the cases of two labelings, SIBO matroids, matroids representable over a fixed, finite field, and sparse paving matroids.
Cite as

Dániel Garamvölgyi, Ryuhei Mizutani, Taihei Oki, Tamás Schwarcz, and Yutaro Yamaguchi. Towards the Proximity Conjecture on Group-Labeled Matroids. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 85:1-85:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{garamvolgyi_et_al:LIPIcs.ICALP.2025.85,
  author =	{Garamv\"{o}lgyi, D\'{a}niel and Mizutani, Ryuhei and Oki, Taihei and Schwarcz, Tam\'{a}s and Yamaguchi, Yutaro},
  title =	{{Towards the Proximity Conjecture on Group-Labeled Matroids}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{85:1--85:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.85},
  URN =		{urn:nbn:de:0030-drops-234628},
  doi =		{10.4230/LIPIcs.ICALP.2025.85},
  annote =	{Keywords: sparse paving matroid, subsequence-interchangeable base orderability, congruency constraint, multiple labelings}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.99
Algorithmic Aspects of Semistability of Quiver Representations

Authors: Yuni Iwamasa, Taihei Oki, and Tasuku Soma

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We study the semistability of quiver representations from an algorithmic perspective. We present efficient algorithms for several fundamental computational problems on the semistability of quiver representations: deciding the semistability and σ-semistability, finding the maximizers of King’s criterion, and computing the Harder-Narasimhan filtration. We also investigate a class of polyhedral cones defined by the linear system in King’s criterion, which we refer to as King cones. For rank-one representations, we demonstrate that these King cones can be encoded by submodular flow polytopes, enabling us to decide the σ-semistability in strongly polynomial time. Our approach employs submodularity in quiver representations, which may be of independent interest.
Cite as

Yuni Iwamasa, Taihei Oki, and Tasuku Soma. Algorithmic Aspects of Semistability of Quiver Representations. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 99:1-99:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{iwamasa_et_al:LIPIcs.ICALP.2025.99,
  author =	{Iwamasa, Yuni and Oki, Taihei and Soma, Tasuku},
  title =	{{Algorithmic Aspects of Semistability of Quiver Representations}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{99:1--99:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.99},
  URN =		{urn:nbn:de:0030-drops-234762},
  doi =		{10.4230/LIPIcs.ICALP.2025.99},
  annote =	{Keywords: quivers, \sigma-semistability, King’s criterion, operator scaling, submodular flow}
}
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
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.86
Problems on Group-Labeled Matroid Bases

Authors: Florian Hörsch, András Imolay, Ryuhei Mizutani, Taihei Oki, and Tamás Schwarcz

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
Consider a matroid equipped with a labeling of its ground set to an abelian group. We define the label of a subset of the ground set as the sum of the labels of its elements. We study a collection of problems on finding bases and common bases of matroids with restrictions on their labels. For zero bases and zero common bases, the results are mostly negative. While finding a non-zero basis of a matroid is not difficult, it turns out that the complexity of finding a non-zero common basis depends on the group. Namely, we show that the problem is hard for a fixed group if it contains an element of order two, otherwise it is polynomially solvable. As a generalization of both zero and non-zero constraints, we further study F-avoiding constraints where we seek a basis or common basis whose label is not in a given set F of forbidden labels. Using algebraic techniques, we give a randomized algorithm for finding an F-avoiding common basis of two matroids represented over the same field for finite groups given as operation tables. The study of F-avoiding bases with groups given as oracles leads to a conjecture stating that whenever an F-avoiding basis exists, an F-avoiding basis can be obtained from an arbitrary basis by exchanging at most |F| elements. We prove the conjecture for the special cases when |F| ≤ 2 or the group is ordered. By relying on structural observations on matroids representable over fixed, finite fields, we verify a relaxed version of the conjecture for these matroids. As a consequence, we obtain a polynomial-time algorithm in these special cases for finding an F-avoiding basis when |F| is fixed.
Cite as

Florian Hörsch, András Imolay, Ryuhei Mizutani, Taihei Oki, and Tamás Schwarcz. Problems on Group-Labeled Matroid Bases. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 86:1-86:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{horsch_et_al:LIPIcs.ICALP.2024.86,
  author =	{H\"{o}rsch, Florian and Imolay, Andr\'{a}s and Mizutani, Ryuhei and Oki, Taihei and Schwarcz, Tam\'{a}s},
  title =	{{Problems on Group-Labeled Matroid Bases}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{86:1--86:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.86},
  URN =		{urn:nbn:de:0030-drops-202299},
  doi =		{10.4230/LIPIcs.ICALP.2024.86},
  annote =	{Keywords: matroids, matroid intersection, congruency constraint, exact-weight constraint, additive combinatorics, algebraic algorithm, strongly base orderability}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.89
On Solving (Non)commutative Weighted Edmonds' Problem

Authors: Taihei Oki

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
In this paper, we consider computing the degree of the Dieudonné determinant of a polynomial matrix A = A_l + A_{l-1} s + ⋯ + A₀ s^l, where each A_d is a linear symbolic matrix, i.e., entries of A_d are affine functions in symbols x₁, …, x_m over a field K. This problem is a natural "weighted analog" of Edmonds' problem, which is to compute the rank of a linear symbolic matrix. Regarding x₁, …, x_m as commutative or noncommutative, two different versions of weighted and unweighted Edmonds' problems can be considered. Deterministic polynomial-time algorithms are unknown for commutative Edmonds' problem and have been proposed recently for noncommutative Edmonds' problem. The main contribution of this paper is to establish a deterministic polynomial-time reduction from (non)commutative weighted Edmonds' problem to unweighed Edmonds' problem. Our reduction makes use of the discrete Legendre conjugacy between the integer sequences of the maximum degree of minors of A and the rank of linear symbolic matrices obtained from the coefficient matrices of A. Combined with algorithms for noncommutative Edmonds' problem, our reduction yields the first deterministic polynomial-time algorithm for noncommutative weighted Edmonds' problem with polynomial bit-length bounds. We also give a reduction of the degree computation of quasideterminants and its application to the degree computation of noncommutative rational functions.
Cite as

Taihei Oki. On Solving (Non)commutative Weighted Edmonds' Problem. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 89:1-89:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{oki:LIPIcs.ICALP.2020.89,
  author =	{Oki, Taihei},
  title =	{{On Solving (Non)commutative Weighted Edmonds' Problem}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{89:1--89:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.89},
  URN =		{urn:nbn:de:0030-drops-124963},
  doi =		{10.4230/LIPIcs.ICALP.2020.89},
  annote =	{Keywords: skew fields, Edmonds' problem, Dieudonn\'{e} determinant, degree computation, Smith - McMillan form, matrix expansion, discrete Legendre conjugacy}
}
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact