9 citations · 18 across the 8 of their papers we have counts for
4 papers · 1 filter
Fast Fourier Sparsity Testing
Grigory Yaroslavtsev, Samson Zhou
A function is -sparse if it has at most non-zero Fourier coefficients. Motivated by applications to fast sparse Fourier transforms over $…
"Bring Your Own Greedy"+Max: Near-Optimal -Approximations for Submodular Knapsack
Dmitrii Avdiukhin, Grigory Yaroslavtsev, Samson Zhou
The problem of selecting a small-size representative summary of a large dataset is a cornerstone of machine learning, optimization and data science. Motivated by applications to re…
Approximate -Sketching of Valuation Functions
Grigory Yaroslavtsev, Samson Zhou
We study the problem of constructing a linear sketch of minimum dimension that allows approximation of a given real-valued function …
Adversarially Robust Submodular Maximization under Knapsack Constraints
Dmitrii Avdiukhin, Slobodan Mitrović, Grigory Yaroslavtsev +1
We propose the first adversarially robust algorithm for monotone submodular maximization under single and multiple knapsack constraints with scalable implementations in distributed…