  A number of recent results on optimization problems involving submodular
functions have made use of the multilinear relaxation of the problem. These
results hold typically in the value oracle model, where the objective function
is accessible via a black box returning f(S) for a given S. We present a
general approach to deriving inapproximability results in the value oracle
model, based on the notion of symmetry gap. Our main result is that for any
fixed instance that exhibits a certain symmetry gap in its multilinear
relaxation, there is a naturally related class of instances for which a better
approximation factor than the symmetry gap would require exponentially many
oracle queries. This unifies several known hardness results for submodular
maximization, and implies several new ones. In particular, we prove that there
is no constant-factor approximation for the problem of maximizing a
non-negative submodular function over the bases of a matroid. We also provide a
closely matching approximation algorithm for this problem.
