  Submodular functions are discrete functions that model laws of diminishing
returns and enjoy numerous algorithmic applications. They have been used in
many areas, including combinatorial optimization, machine learning, and
economics. In this work we study submodular functions from a learning theoretic
angle. We provide algorithms for learning submodular functions, as well as
lower bounds on their learnability. In doing so, we uncover several novel
structural results revealing ways in which submodular functions can be both
surprisingly structured and surprisingly unstructured. We provide several
concrete implications of our work in other domains including algorithmic game
theory and combinatorial optimization.
  At a technical level, this research combines ideas from many areas, including
learning theory (distributional learning and PAC-style analyses), combinatorics
and optimization (matroids and submodular functions), and pseudorandomness
(lossless expander graphs).
