Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: On the power of choice for Boolean functions   In this paper we consider a variant of the well-known Achlioptas process for
graphs adapted to monotone Boolean functions. Fix a number of choices $r\in
\mathbb N$ and a sequence of increasing functions $(f_n)_{n\ge 1}$ such that,
for every $n\ge 1$, $f_n:\{0,1\}^n\mapsto \{0,1\}$. Given $n$ bits which are
all initially equal to 0, at each step $r$ 0-bits are sampled uniformly at
random and are proposed to an agent. Then, the agent selects one of the
proposed bits and turns it from 0 to 1 with the goal to reach the preimage of 1
as quickly as possible. We nearly characterize the conditions under which an
acceleration by a factor of $r(1+o(1))$ is possible, and underline the wide
applicability of our results by giving examples from the fields of Boolean
functions and graph theory.

36
The categories of this paper are: cmp-lg
25
The categories of this paper are: patt-sol
0
The categories of this paper are: hep-ph
19
The categories of this paper are: eess
21
The categories of this paper are: adap-org
32
The categories of this paper are: atom-ph
5
The categories of this paper are: gr-qc
27
The categories of this paper are: comp-gas
31
The categories of this paper are: ao-sci
35
The categories of this paper are: mtrl-th
22
The categories of this paper are: chao-dyn
6
The categories of this paper are: astro-ph
24
The categories of this paper are: dg-ga
9
The categories of this paper are: nlin
37
The categories of this paper are: supr-con
3
The categories of this paper are: physics