3.4k citations · 3.9k across the 67 of their papers we have counts for
4 papers · 1 filter
Lipschitz Continuous Algorithms for Graph Problems
Soh Kumabe, Yuichi Yoshida
Graph algorithms are widely used for decision making and knowledge discovery. To ensure their effectiveness, it is essential that their output remains stable even when subjected to…
Sublinear-Time Algorithms for Max Cut, Max E2Lin, and Unique Label Cover on Expanders
Pan Peng, Yuichi Yoshida
We show sublinear-time algorithms for Max Cut and Max E2Lin on expanders in the adjacency list model that distinguishes instances with the optimal value more than $1-\varepsil…
Low Degree Testing over the Reals
Vipul Arora, Arnab Bhattacharyya, Noah Fleming +2
We study the problem of testing whether a function is a polynomial of degree at most in the \emph{distribution-free} testing model. Here, the d…
Sparsification of Decomposable Submodular Functions
Akbar Rafiey, Yuichi Yoshida
Submodular functions are at the core of many machine learning and data mining tasks. The underlying submodular functions for many of these tasks are decomposable, i.e., they are su…