4 papers
Low-Sensitivity Matching via Sampling from Gibbs Distributions
Yuichi Yoshida, Zihan Zhang
In this work, we study the maximum matching problem from the perspective of sensitivity. The sensitivity of an algorithm on a graph is defined as the maximum Wasserstein di…
From Generative to Episodic: Sample-Efficient Replicable Reinforcement Learning
Max Hopkins, Sihan Liu, Christopher Ye +1
The epidemic failure of replicability across empirical science and machine learning has recently motivated the formal study of replicable learning algorithms [Impagliazzo et al. (2…
-Approximation Algorithms for Bipartiteness Ratio
Tasuku Soma, Mingquan Ye, Yuichi Yoshida
We propose an -approximation algorithm for the bipartiteness ratio of undirected graphs introduced by Trevisan (SIAM Journal on Computing, vol. 41, no. 6, 2012), where $…
Sensitivity Lower Bounds for Approximaiton Algorithms
Noah Fleming, Yuichi Yoshida
Sensitivity measures how much the output of an algorithm changes, in terms of Hamming distance, when part of the input is modified. While approximation algorithms with low sensitiv…