Tatsuya Terao

Tatsuya Terao

Auto-generated profile, based on publicly available information

Tatsuya Terao

Research Institute for Mathematical Sciences Kyoto University

Research Focus & Metrics

Academic Career Length

4Years (2023-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
6 January 2025 in ACM Transactions on Algorithms
Verified
Journal Article
Open access
TTTatsuya Terao
Tatsuya Terao
In the matroid partitioning problem, we are given \(k\) matroids \(\mathcal{M}_{1}=(V,\mathcal{I}_{1}),\dots,\mathcal{M}_{k}=(V,\mathcal{I}_{k})\) defined over a common ground set \(V\) of \(n\) elements, and we need to find a partitionable set \(S\subseteq V\) of largest possible cardinality, denoted by \(p\) . Here, a set \(S\subseteq V\) is called partitionable if there exists a partition \((S_{1},\dots,S_{k})\) of \(S\) with \(S_{i}\in\mathcal{I}_{i}\) for \(i=1,\ldots,k\) . In 1986, Cunningham presented a matroid partition algorithm that uses \(O(np^{3/2}+kn)\) independence oracle queries, which was the previously known best algorithm. This query complexity is \(O(n^{5/2})\) when \(k\leq n\) . Our main result is to present a matroid partition algorithm that uses \(\tilde{O}(k^{\prime 1/3}np + kn)\) independence oracle queries, where \(k^{\prime}=\min\{k,p\}\) . This query complexity is \(\tilde{O}(n^{7/3})\) when \(k\leq n\) , which improves upon that of Cunningham’s algorithm. To obtain our algorithm, we present a new approach edge recycling augmentation , which can be attained through new ideas: an efficient utilization of the binary search technique by Nguy \(\tilde{{\hat{\text{e}}}}\) n and Chakrabarty et al. and a careful analysis of the independence oracle query complexity. Our analysis differs significantly from the one for matroid intersection algorithms, because of the parameter \(k\) . We also present a matroid partition algorithm that uses \(\tilde{O}((n+k)\sqrt{p})\) rank oracle queries.

13 June 2026
Verified
Book Chapter
Closed access
CHChien-Chung Huang
Chien-Chung Huang
NKNaonori Kakimura
Naonori Kakimura
YKYusuke Kobayashi
Yusuke Kobayashi
TTTatsuya Terao
Tatsuya Terao

1 December 2023 in arXiv
Verified
Preprint
Open access
PDF file
TTTatsuya Terao
Tatsuya Terao
In the matroid partitioning problem, we are given $k$ matroids $\mathcal{M}_1 = (V, \mathcal{I}_1), \dots , \mathcal{M}_k = (V, \mathcal{I}_k)$ defined over a common ground set $V$ of $n$ elements, and we need to find a partitionable set $S \subseteq V$ of largest possible cardinality, denoted by $p$. Here, a set $S \subseteq V$ is called partitionable if there exists a partition $(S_1, \dots , S_k)$ of $S$ with $S_i \in \mathcal{I}_i$ for $i = 1, \ldots, k$. In 1986, Cunningham [SICOMP 1986] presented a matroid partition algorithm that uses $O(n p^{3/2} + k n)$ independence oracle queries, which was the previously known best algorithm. This query complexity is $O(n^{5/2})$ when $k \leq n$. Our main result is to present a matroid partition algorithm that uses $\tilde{O}(k'^{1/3} n p + k n)$ independence oracle queries, where $k' = \min\{k, p\}$. This query complexity is $\tilde{O}(n^{7/3})$ when $k \leq n$, and this improves upon the one of previous Cunningham's algorithm. To obtain this, we present a new approach \emph{edge recycling augmentation}, which can be attained through new ideas: an efficient utilization of the binary search technique by Nguyen [2019] and Chakrabarty-Lee-Sidford-Singla-Wong [FOCS 2019] and a careful analysis of the independence oracle query complexity. Our analysis differs significantly from the one for matroid intersection algorithms, because of the parameter $k$. We also present a matroid partition algorithm that uses $\tilde{O}((n + k) \sqrt{p})$ rank oracle queries.

7 August 2024 in arXiv
Verified
Preprint
Open access
PDF file
TTTatsuya Terao
Tatsuya Terao
RMRyuhei Mori
Ryuhei Mori
In this paper, we consider the parameterized quantum query complexity for graph problems. We design parameterized quantum query algorithms for $k$-vertex cover and $k$-matching problems, and present lower bounds on the parameterized quantum query complexity. Then, we show that our quantum query algorithms are optimal up to a constant factor when the parameters are small.