On the power of choice for Boolean functions

DOI10.1137/21M1449245zbMATH Open1497.94218arXiv2109.13079OpenAlexW3204901460WikidataQ113779014 ScholiaQ113779014MaRDI QIDQ5099100FDOQ5099100

Authors: Nicolas Fraiman, Lyuben Lichev, D. Mitsche 

Publication date: 31 August 2022

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

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.

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

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

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)

Cites Work

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

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)