On the power of choice for Boolean functions

09/27/2021
by   Nicolas Fraiman, et al.
0

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∈ℕ and a sequence of increasing functions (f_n)_n≥ 1 such that, for every n≥ 1, f_n:{0,1}^n↦{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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset