Tight Bounds on Low-Degree Spectral Concentration of Submodular and XOS Functions.

Vitaly Feldman Jan Vondrák

Published in: FOCS (2015)

Keyphrases

tight bounds
low degree
upper bound
greedy algorithm
objective function
threshold functions
machine learning
lower bound
decision lists