3.4k citations · 3.9k across the 67 of their papers we have counts for
6 papers · 1 filter
On the three graph invariants related to matching of finite simple graphs
Kazunori Matsuda, Yuichi Yoshida
Let be a finite simple graph on the vertex set and let , and denote the induced matching number, the minimum…
Average Sensitivity of Dynamic Programming
Soh Kumabe, Yuichi Yoshida
When processing data with uncertainty, it is desirable that the output of the algorithm is stable against small perturbations in the input. Varma and Yoshida [SODA'21] recently for…
Local Algorithms for Estimating Effective Resistance
Pan Peng, Daniel Lopatta, Yuichi Yoshida +1
Effective resistance is an important metric that measures the similarity of two vertices in a graph. It has found applications in graph clustering, recommendation systems and netwo…
Spectral Hypergraph Sparsifiers of Nearly Linear Size
Michael Kapralov, Robert Krauthgamer, Jakab Tardos +1
Graph sparsification has been studied extensively over the past two decades, culminating in spectral sparsifiers of optimal size (up to constant factors). Spectral hypergraph spars…
Online Risk-Averse Submodular Maximization
Tasuku Soma, Yuichi Yoshida
We present a polynomial-time online algorithm for maximizing the conditional value at risk (CVaR) of a monotone stochastic submodular function. Given i.i.d. samples from an und…
RelWalk A Latent Variable Model Approach to Knowledge Graph Embedding
Danushka Bollegala, Huda Hakami, Yuichi Yoshida +1
Embedding entities and relations of a knowledge graph in a low-dimensional space has shown impressive performance in predicting missing links between entities. Although progresses…