A few lower bounds are known for monotone functions in the adversarial order model:
with a weak oracle, any \((1/2+\epsilon )\) -approximation would require \(\Omega (n/k)\)  memory [1]}. Under a strong oracle, a lower bound of \(\Omega (n/k^3)\)  memory for any \((1/2+\epsilon )\) -approximation algorithm was shown in a recent paper by Feldman et al. [2]}.
Another recent lower bound was proved by McGregor and Vu [3]}: a \((1-1/e+\varepsilon )\) -approximation for coverage functions requires \(\Omega (n/k^2)\)  memory (this lower bound holds for explicitly given inputs, via communication complexity; we note that this is incomparable to the computational \((1-1/e+\varepsilon )\) -hardness of maximum coverage [4]}). For non-monotone functions, Alaluf et al. [5]} proved an \(\Omega (n)\)  memory lower bound for the adversarial order model with unbounded computation.
