On the power of choice for Boolean functions

Abstract

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.