Trade-offs between Selection Complexity and Performance when Searching the Plane without Communication∗

We argue that in the context of biology-inspired problems in computer science, in addition to studying the time com-plexity of solutions it is also important to study the selec-tion complexity, a measure of how likely a given algorithmic strategy is to arise in nature. In this spirit, we propose a selection complexity metric χ for the ANTS problem [Fein-erman et al.]. For algorithm A, we define χ(A) = b + log `, where b is the number of memory bits used by each agent and ` bounds the fineness of available probabilities (agents use probabilities of at least 1/2`). We consider n agents searching for a target in the plane, within an (unknown) distance D from the origin. We iden-tify log logD as a crucial threshold for our selection com-plexity metric. We prove a new upper bound that achieves near-optimal speed-up of (D2/n + D) · 2O(`) for χ(A) ≤ 3 log logD + O(1), which is asymptotically optimal if ` ∈ O(1). By comparison, previous algorithms achieving simi-lar speed-up require χ(A) = Ω(logD). We show that this threshold is tight by proving that if χ(A) < log logD−ω(1), then with high probability the target is not found if each agent performs D2−o(1) moves. This constitutes a sizable gap to the straightforward Ω(D2/n+D) lower bound