  We consider the classical problem of maximizing a monotone submodular
function subject to a cardinality constraint, which, due to its numerous
applications, has recently been studied in various computational models. We
consider a clean multi-player model that lies between the offline and streaming
model, and study it under the aspect of one-way communication complexity. Our
model captures the streaming setting (by considering a large number of
players), and, in addition, two player approximation results for it translate
into the robust setting. We present tight one-way communication complexity
results for our model, which, due to the above-mentioned connections, have
multiple implications in the data stream and robust setting.
  Even for just two players, a prior information-theoretic hardness result
implies that no approximation factor above $1/2$ can be achieved in our model,
if only queries to feasible sets are allowed. We show that the possibility of
querying infeasible sets can actually be exploited to beat this bound, by
presenting a tight $2/3$-approximation taking exponential time, and an
efficient $0.514$-approximation. To the best of our knowledge, this is the
first example where querying a submodular function on infeasible sets leads to
provably better results. Through the above-mentioned link to the robust
setting, both of these algorithms improve on the current state-of-the-art for
robust submodular maximization, showing that approximation factors beyond $1/2$
are possible. Moreover, exploiting the link of our model to streaming, we
settle the approximability for streaming algorithms by presenting a tight
$1/2+\varepsilon$ hardness result, based on the construction of a new family of
coverage functions. This improves on a prior $1-1/e+\varepsilon$ hardness and
matches, up to an arbitrarily small margin, the best known approximation
algorithm.
