On the power of choice for Boolean functions

DOI10.1137/21M1449245MaRDI QIDQ5099100zbMATH OpenOpenAlexWikidataFDO

Authors Nicolas Fraiman, Lyuben Lichev, D. Mitsche

Publication date 31 August 2022

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2109.13079

zbMATH Keywords

thresholdrandomized algorithmBoolean functionhitting probabilityAchlioptas processpower of choicerelevant variable

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Randomized algorithms (68W20) General topics of discrete mathematics in relation to computer science (68R01) Boolean functions (06E30) Stochastic processes (60G99) Boolean functions (94D10)

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 $rinmathbbN$ and a sequence of increasing functions $(f_n{)}_{nge1}$ such that, for every $nge1$, $f_n:{0,1}^{n}mapsto0,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.

Recommendations

• The power of choice for random satisfiability
• The Boolean functions computed by random Boolean formulas or how to grow the right function
• Sharp thresholds for monotone non-Boolean functions and social choice theory
• Random \(k\)-SAT and the power of two choices
• Small subgraphs in random graphs and the power of multiple choices

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• A power-of-two-choices unbalanced allocation process
• Achlioptas process phase transitions are continuous
• Avoiding a giant component
• Avoiding small subgraphs in Achlioptas processes
• Balanced Allocations
• Balanced Allocations: The Heavily Loaded Case
• Balanced allocation on graphs
• Birth control for giants
• Combinatorics in the exterior algebra and the Bollobás two families theorem
• Creating small subgraphs in Achlioptas processes with growing parameter
• Delaying satisfiability for random 2SAT
• Every monotone graph property has a sharp threshold
• Explosive percolation in random networks
• Hamiltonicity thresholds in Achlioptas processes
• Memoryless rules for Achlioptas processes
• Random \(k\)-SAT and the power of two choices
• Random graphs.
• Semi-random graph process
• Threshold functions

Cited in

(2)

• A structure theorem for Boolean functions with small total influences
• On the computational power of Boolean decision lists

This page was built for publication: On the power of choice for Boolean functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5099100)