3.4k citations · 3.9k across the 67 of their papers we have counts for
51 papers · 1 filter
Beyond Cut Balance: Spectral Sparsification of the Nonlinear Directed Laplacian
Yuichi Yoshida
Digraphs with constant cut balance admit nearly linear directed cut sparsifiers. This condition requires the total arc weights in the two directions of every cut to be within a con…
Tolerant Testing for Unique Games
Yuichi Yoshida
We give tolerant testers with sublinear query complexity in the adjacency-list model for Unique Games. Prior tolerant testers required structural assumptions such as expansion or c…
Solving Hypergraph Laplacian Systems in Almost-Linear Time
Yuichi Yoshida
For a connected weighted hypergraph, we give a randomized almost-linear-time solver for the Poisson problem for the cut-based hypergraph Laplacian in the natural input size $P=\sum…
Lower Bounds for Testing Directed Acyclicity in the Unidirectional Bounded-Degree Model
Yuichi Yoshida
We study property testing of directed acyclicity in the unidirectional bounded-degree oracle model, where a query to a vertex reveals its outgoing neighbors. We prove that there ex…
Non-Signaling Locality Lower Bounds for Dominating Set
Noah Fleming, Max Hopkins, Yuichi Yoshida
Minimum dominating set is a basic local covering problem and a core task in distributed computing. Despite extensive study, in the classic LOCAL model there exist significant gaps…
Average sensitivity of the Knapsack Problem
Soh Kumabe, Yuichi Yoshida
In resource allocation, we often require that the output allocation of an algorithm is stable against input perturbation because frequent reallocation is costly and untrustworthy.…