Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Leaderless Population Protocols Decide Double-exponential Thresholds   Population protocols are a model of distributed computation in which
finite-state agents interact randomly in pairs. A protocol decides for any
initial configuration whether it satisfies a fixed property, specified as a
predicate on the set of configurations. The state complexity of a predicate is
smallest number of states of any protocol deciding that predicate. For
threshold predicates of the form $x\ge k$, with $k$ constant, prior work has
shown that they have state complexity $\Theta(\log\log k)$ if the protocol is
extended with leaders. For ordinary protocols it is only known to be in
$\Omega(\log\log k)\cap \mathcal{O}(\log k)$. We close this remaining gap by
showing that it is $\Theta(\log\log k)$ as well, i.e. we construct protocols
with $\mathcal{O}(n)$ states deciding $x\ge k$ with $k\ge2^{2^n}$.

33
The categories of this paper are: plasm-ph
32
The categories of this paper are: atom-ph
4
The categories of this paper are: cond-mat
3
The categories of this paper are: physics
10
The categories of this paper are: q-bio
18
The categories of this paper are: econ
17
The categories of this paper are: q-fin
12
The categories of this paper are: nucl-th
35
The categories of this paper are: mtrl-th
27
The categories of this paper are: comp-gas
15
The categories of this paper are: nucl-ex
34
The categories of this paper are: chem-ph
0
The categories of this paper are: hep-ph
28
The categories of this paper are: alg-geom
30
The categories of this paper are: q-alg
21
The categories of this paper are: adap-org