A note on concentration of submodular functions
read the original abstract
We survey a few concentration inequalities for submodular and fractionally subadditive functions of independent random variables, implied by the entropy method for self-bounding functions. The power of these concentration bounds is that they are dimension-free, in particular implying standard deviation O(\sqrt{\E[f]}) rather than O(\sqrt{n}) which can be obtained for any 1-Lipschitz function of n variables.
This paper has not been read by Pith yet.
Forward citations
Cited by 2 Pith papers
-
Non-Adaptive Cryptanalytic Time-Space Lower Bounds via a Shearer-like Inequality for Permutations
Non-adaptive preprocessing for discrete log and similar problems cannot beat O(sqrt(N)) online time without Omega(sqrt(N)) advice bits, proven via a Shearer-like inequality for permutations.
-
Efficient Algorithms for Influence Maximization in General Models and Observed Cascades
Develops low-adaptivity framework and sketching techniques yielding nearly-linear time algorithms with guarantees for influence maximization on observed cascades, plus an improved tail bound for the independent cascade model.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.