  We introduce a novel framework of Prophet Inequalities for combinatorial
valuation functions. For a (non-monotone) submodular objective function over an
arbitrary matroid feasibility constraint, we give an $O(1)$-competitive
algorithm. For a monotone subadditive objective function over an arbitrary
downward-closed feasibility constraint, we give an $O(\log n \log^2
r)$-competitive algorithm (where $r$ is the cardinality of the largest feasible
subset).
  Inspired by the proof of our subadditive prophet inequality, we also obtain
an $O(\log n \cdot \log^2 r)$-competitive algorithm for the Secretary Problem
with a monotone subadditive objective function subject to an arbitrary
downward-closed feasibility constraint. Even for the special case of a
cardinality feasibility constraint, our algorithm circumvents an
$\Omega(\sqrt{n})$ lower bound by Bateni, Hajiaghayi, and Zadimoghaddam
\cite{BHZ13-submodular-secretary_original} in a restricted query model.
  En route to our submodular prophet inequality, we prove a technical result of
independent interest: we show a variant of the Correlation Gap Lemma for
non-monotone submodular functions.
