English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Initial knowledge regarding group size can be crucial for collectiveperformance. We study this relation in the context of the {\em Ants NearbyTreasure Search (ANTS)} problem \cite{FKLS}, which models natural cooperativeforaging behavior such as that performed by ants around their nest. In thisproblem, $k$ (probabilistic) agents, initially placed at some central location,collectively search for a treasure on the two-dimensional grid. The treasure isplaced at a target location by an adversary and the goal is to find it as fastas 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 agentsknow their total number $k$ (or a constant approximation of it), and enoughmemory bits are available at their disposal \cite{FKLS}. In this paper, weestablish lower bounds on the agent memory size required for achieving certainrunning time performances. To the best our knowledge, these bounds are thefirst non-trivial lower bounds for the memory size of probabilistic searchers.For example, for every given positive constant $\epsilon$, terminating thesearch by time $O(\log^{1-\epsilon} k \cdot T)$ requires agents to use$\Omega(\log\log k)$ memory bits. Such distributed computing bounds may providea novel, strong tool for the investigation of complex biological systems.

Memory Lower Bounds for Randomized Collaborative Search and Applications to Biology