  Initial knowledge regarding group size can be crucial for collective
performance. We study this relation in the context of the {\em Ants Nearby
Treasure Search (ANTS)} problem \cite{FKLS}, which models natural cooperative
foraging behavior such as that performed by ants around their nest. In this
problem, $k$ (probabilistic) agents, initially placed at some central location,
collectively search for a treasure on the two-dimensional grid. The treasure is
placed at a target location by an adversary and the goal is to find it as fast
as possible as a function of both $k$ and $D$, where $D$ is the (unknown)
distance between the central location and the target. It is easy to see that
$T=\Omega(D+D^2/k)$ time units are necessary for finding the treasure.
Recently, it has been established that $O(T)$ time is sufficient if the agents
know their total number $k$ (or a constant approximation of it), and enough
memory bits are available at their disposal \cite{FKLS}. In this paper, we
establish lower bounds on the agent memory size required for achieving certain
running time performances. To the best our knowledge, these bounds are the
first non-trivial lower bounds for the memory size of probabilistic searchers.
For example, for every given positive constant $\epsilon$, terminating the
search by time $O(\log^{1-\epsilon} k \cdot T)$ requires agents to use
$\Omega(\log\log k)$ memory bits. Such distributed computing bounds may provide
a novel, strong tool for the investigation of complex biological systems.
