3.4k citations · 3.9k across the 67 of their papers we have counts for
4 papers · 2 filters
A Characterization of Constant-Sample Testable Properties
Eric Blais, Yuichi Yoshida
We characterize the set of properties of Boolean-valued functions on a finite domain that are testable with a constant number of samples. Specifically, we show that a…
Non-monotone DR-Submodular Function Maximization
Tasuku Soma, Yuichi Yoshida
We consider non-monotone DR-submodular function maximization, where DR-submodularity (diminishing return submodularity) is an extension of submodularity for functions over the inte…
Testing Assignments to Constraint Satisfaction Problems
Hubie Chen, Matt Valeriote, Yuichi Yoshida
For a finite relational structure A, let CSP(A) denote the CSP instances whose constraint relations are taken from A. The resulting family of problems CSP(A) has been considered he…
Maximizing a Monotone Submodular Function with a Bounded Curvature under a Knapsack Constraint
Yuichi Yoshida
We consider the problem of maximizing a monotone submodular function under a knapsack constraint. We show that, for any fixed , there exists a polynomial-time algorithm with…