7 papers
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…
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…