3.4k citations · 3.9k across the 67 of their papers we have counts for
10 papers · 1 filter
Towards Tight Bounds for Spectral Sparsification of Hypergraphs
Michael Kapralov, Robert Krauthgamer, Jakab Tardos +1
Cut and spectral sparsification of graphs have numerous applications, including e.g. speeding up algorithms for cuts and Laplacian solvers. These powerful notions have recently bee…
Sensitivity Analysis of Submodular Function Maximization
Conor McMeel, Yuichi Yoshida
We study the recently introduced idea of worst-case sensitivity for monotone submodular maximization with cardinality constraint , which captures the degree to which the output…
Sensitivity Analysis of the Maximum Matching Problem
Yuichi Yoshida, Samson Zhou
We consider the sensitivity of algorithms for the maximum matching problem against edge and vertex modifications. Algorithms with low sensitivity are desirable because they are rob…
Downsampling for Testing and Learning in Product Distributions
Nathaniel Harms, Yuichi Yoshida
We study distribution-free property testing and learning problems where the unknown probability distribution is a product distribution over . For many important class…
Fast and Private Submodular and -Submodular Functions Maximization with Matroid Constraints
Akbar Rafiey, Yuichi Yoshida
The problem of maximizing nonnegative monotone submodular functions under a certain constraint has been intensively studied in the last decade, and a wide range of efficient approx…
Hypergraph Clustering Based on PageRank
Yuuki Takai, Atsushi Miyauchi, Masahiro Ikeda +1
A hypergraph is a useful combinatorial object to model ternary or higher-order relations among entities. Clustering hypergraphs is a fundamental task in network analysis. In this s…