3 Search Results for "Storjohann, Arne"

Document
DOI: 10.4230/LIPIcs.SWAT.2026.39
Faster Approximate Linear Matroid Intersection

Authors: Tatsuya Terao

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
We consider a fast approximation algorithm for the linear matroid intersection problem. In this problem, we are given two r × n matrices M₁ and M₂, and the objective is to find a largest set of columns that are linearly independent in both M₁ and M₂. We design a (1 - ε)-approximation algorithm with time complexity Õ_{ε}(nnz(M₁) + nnz(M₂) + r_{*}^{ω}), where nnz(M_i) denotes the number of nonzero entries in M_i for i = 1, 2, r_{*} denotes the maximum size of a common independent set, and ω < 2.372 denotes the matrix multiplication exponent. Our approximation algorithm is faster than the exact algorithm by Harvey [FOCS'06 & SICOMP'09] and Cheung-Kwok-Lau [STOC'12 & JACM'13], which runs in Õ(nnz(M₁) + nnz(M₂) + n r_{*}^{ω - 1}) time. We also develop a fast (1 - ε)-approximation algorithm for the weighted version of the linear matroid intersection problem. In fact, we design a (1 - ε)-approximation algorithm for weighted linear matroid intersection with time complexity Õ_{ε}(nnz(M₁) + nnz(M₂) + r_{*}^{ω}). Our algorithm improves upon the (1 - ε)-approximation algorithm by Huang-Kakimura-Kamiyama [SODA'16 & Math. Program.'19], which runs in Õ_{ε}(nnz(M₁) + nnz(M₂) + nr_{*}^{ω - 1}) time. To obtain these results, we combine Quanrud’s adaptive sparsification framework [ICALP'24] with a simple yet effective method for efficiently checking whether a given vector lies in the linear span of a subset of vectors, which is of independent interest.
Cite as

Tatsuya Terao. Faster Approximate Linear Matroid Intersection. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 39:1-39:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{terao:LIPIcs.SWAT.2026.39,
  author =	{Terao, Tatsuya},
  title =	{{Faster Approximate Linear Matroid Intersection}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{39:1--39:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.39},
  URN =		{urn:nbn:de:0030-drops-260756},
  doi =		{10.4230/LIPIcs.SWAT.2026.39},
  annote =	{Keywords: Linear matroid intersection, fast approximation algorithm}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.59
Deciding Local Unitary Equivalence of Graph States in Quasi-Polynomial Time

Authors: Nathan Claudet and Simon Perdrix

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

Abstract
We describe an algorithm with quasi-polynomial runtime n^{log₂(n)+O(1)} for deciding local unitary (LU) equivalence of graph states. The algorithm builds on a recent graphical characterisation of LU-equivalence via generalised local complementation. By first transforming the corresponding graphs into a standard form using usual local complementations, LU-equivalence reduces to the existence of a single generalised local complementation that maps one graph to the other. We crucially demonstrate that this reduces to solving a system of quasi-polynomially many linear equations, avoiding an exponential blow-up. As a byproduct, we generalise Bouchet’s algorithm for deciding local Clifford (LC) equivalence of graph states by allowing the addition of arbitrary linear constraints. We also improve existing bounds on the size of graph states that are LU- but not LC-equivalent. While the smallest known examples involve 27 qubits, and it is established that no such examples exist for up to 8 qubits, we refine this bound by proving that LU- and LC-equivalence coincide for graph states involving up to 19 qubits.
Cite as

Nathan Claudet and Simon Perdrix. Deciding Local Unitary Equivalence of Graph States in Quasi-Polynomial Time. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 59:1-59:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{claudet_et_al:LIPIcs.ICALP.2025.59,
  author =	{Claudet, Nathan and Perdrix, Simon},
  title =	{{Deciding Local Unitary Equivalence of Graph States in Quasi-Polynomial Time}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{59:1--59:20},
  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.59},
  URN =		{urn:nbn:de:0030-drops-234367},
  doi =		{10.4230/LIPIcs.ICALP.2025.59},
  annote =	{Keywords: Quantum computing, Graph theory, Entanglement, Local complementation}
}
Document
DOI: 10.4230/DagSemProc.06271.12
Notes on computing minimal approximant bases

Authors: Arne Storjohann

Published in: Dagstuhl Seminar Proceedings, Volume 6271, Challenges in Symbolic Computation Software (2006)

Abstract
We show how to transform the problem of computing solutions to a classical Hermite Pade approximation problem for an input vector of dimension $m imes 1$, arbitrary degree constraints $(n_1,n_2,ldots,n_m)$, and order $N := (n_1 + 1) + cdots + (n_m + 1) - 1$, to that of computing a minimal approximant basis for a matrix of dimension $O(m) imes O(m)$, uniform degree constraint $Theta(N/m)$, and order $Theta(N/m)$.
Cite as

Arne Storjohann. Notes on computing minimal approximant bases. In Challenges in Symbolic Computation Software. Dagstuhl Seminar Proceedings, Volume 6271, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{storjohann:DagSemProc.06271.12,
  author =	{Storjohann, Arne},
  title =	{{Notes on computing minimal approximant bases}},
  booktitle =	{Challenges in Symbolic Computation Software},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6271},
  editor =	{Wolfram Decker and Mike Dewar and Erich Kaltofen and Stephen Watt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06271.12},
  URN =		{urn:nbn:de:0030-drops-7763},
  doi =		{10.4230/DagSemProc.06271.12},
  annote =	{Keywords: Hermite Pade approximation, minimal approximant bases}
}
  • Refine by Type
  • 3 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 1 2025
  • 1 2006

  • Refine by Author
  • 1 Claudet, Nathan
  • 1 Perdrix, Simon
  • 1 Storjohann, Arne
  • 1 Terao, Tatsuya

  • Refine by Series/Journal
  • 2 LIPIcs
  • 1 DagSemProc

  • Refine by Classification
  • 1 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Matroids and greedoids
  • 1 Theory of computation → Algorithm design techniques
  • 1 Theory of computation → Quantum information theory

  • Refine by Keyword
  • 1 Entanglement
  • 1 Graph theory
  • 1 Hermite Pade approximation
  • 1 Linear matroid intersection
  • 1 Local complementation
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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