Tight Bounds on Low-degree Spectral Concentration of Submodular and XOS functions.

Vitaly Feldman Jan Vondrák

Published in: CoRR (2015)

Keyphrases

tight bounds
low degree
upper bound
threshold functions
lower bound
greedy algorithm
uniform distribution
objective function
special case
decision rules
learning theory