3.4k citations · 3.9k across the 67 of their papers we have counts for
75 papers
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…
A quantitative container characterization of one-sided testability
Gaia Carenini, Cameron Seth, Yuichi Yoshida
We give a quantitative combinatorial characterization of size-oblivious one-sided testability in the dense graph model, resolving a question of Alon, Fischer, Newman, and Shapira.…
Nonlinear Laplacians Improve Signed-Directed Graph Learning
Ali Parviz, Yuichi Yoshida
While signed-directed graphs have been studied using linear Laplacians in the design of graph neural networks, relatively little research has focused on developing non-linear Lapla…
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…