Our hardness instances have the following general structure: there is a special subset of \(k\)  good elements, and the remaining \(n-k\)  elements are bad. The good elements are indistinguishable from each other, and ditto for the bad elements. In the monotone case, any \(k\)  bad elements are a \((1-1/e)\) -factor worse than the optimal solution (\(k\)  good elements). Suppose furthermore that for parameter \(r>0\) , as long as we never query the function on a subset with \(\ge r\)  good elements, the good elements are indistinguishable from bad elements.
The only way to collect \(\ge r\)  good elements in the memory buffer is by chance – until we've collected the required number of good elements, they are indistinguishable from bad elements, so the subset in the memory buffer is random.
The classic work of Nemhauser and Wolsey [1]} constructs a pathological monotone submodular function with \(r=\Omega (k)\) , which we use to prove that without memory \(\Omega (n)\)  the algorithm cannot beat \(1-1/e\) .
McGregor and Vu [2]} construct a simple example of a coverage function with \(r=2\) , which we use for our \(\Omega (n/k^2)\)  bound. For an exponential-size ground set, we extend their construction to \(r=3\)  which translates to the improved lower bound of \(\Omega (n/k^{3/2})\) .
