Masataka Yoneda

Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda

We study the problem of online graph coloring for $k$-colorable graphs. The best previously known deterministic algorithm uses $\widetilde{O}(n^{1-\frac{1}{k!}})$ colors for general $k$ and $\widetilde{O}(n^{5/6})$ colors for $k = 4$, both given by Kierstead in 1998. In this paper, we finally break this barrier, achieving the first major improvement in nearly three decades. Our results are summarized as follows: (1) $k \geq 5$ case. We provide a deterministic online algorithm to color $k$-colorable graphs with $\widetilde{O}(n^{1-\frac{1}{k(k-1)/2}})$ colors, significantly improving the current upper bound of $\widetilde{O}(n^{1-\frac{1}{k!}})$ colors. Our algorithm also matches the best-known bound for $k = 4$ ($\widetilde{O}(n^{5/6})$ colors). (2) $k = 4$ case. We provide a deterministic online algorithm to color $4$-colorable graphs with $\widetilde{O}(n^{14/17})$ colors, improving the current upper bound of $\widetilde{O}(n^{5/6})$ colors. (3) $k = 2$ case. We show that for randomized algorithms, the upper bound is $1.034 \log_2 n + O(1)$ colors and the lower bound is $\frac{91}{96} \log_2 n - O(1)$ colors. This means that we close the gap to a factor of $1.09$. With our algorithm for the $k \geq 5$ case, we also obtain a deterministic online algorithm for graph coloring that achieves a competitive ratio of $O(\frac{n}{\log \log n})$, which improves the best-known result of $O(\frac{n \log \log \log n}{\log \log n})$ by Kierstead. For the bipartite graph case ($k = 2$), the limit of online deterministic algorithms is known: any deterministic algorithm requires $2 \log_2 n - O(1)$ colors. Our results imply that randomized algorithms can perform slightly better but still have a limit.

Masataka Yoneda, Yusuke Matsushita, Go Kamoda et al.

We present an ultra-fast and flexible search algorithm that enables search over trillion-scale natural language corpora in under 0.3 seconds while handling semantic variations (substitution, insertion, and deletion). Our approach employs string matching based on suffix arrays that scales well with corpus size. To mitigate the combinatorial explosion induced by the semantic relaxation of queries, our method is built on two key algorithmic ideas: fast exact lookup enabled by a disk-aware design, and dynamic corpus-aware pruning. We theoretically show that the proposed method suppresses exponential growth in the search space with respect to query length by leveraging statistical properties of natural language. In experiments on FineWeb-Edu (Lozhkov et al., 2024) (1.4T tokens), we show that our method achieves significantly lower search latency than existing methods: infini-gram (Liu et al., 2024), infini-gram mini (Xu et al., 2025), and SoftMatcha (Deguchi et al., 2025). As a practical application, we demonstrate that our method identifies benchmark contamination in training corpora, unidentified by existing approaches. We also provide an online demo of fast, soft search across corpora in seven languages.

Hirotaka Yoneda, Masataka Yoneda

We study the problem of online coloring for graphs with large odd girth. The best previously known algorithm uses $O(n^{1/2})$ colors, which was discovered by Kierstead in 1998. This algorithm works when the odd girth is 7 or more. In this paper, we provide the following: for every $\varepsilon > 0$, there exists a constant $g' \in \{3, 5, 7, \dots\}$ such that graphs with odd girth at least $g'$ can be deterministically colored online using $O(n^{\varepsilon})$ colors.