On the Power of Choice for Boolean Functions
DOI10.1137/21M1449245zbMath1497.94218arXiv2109.13079OpenAlexW3204901460WikidataQ113779014 ScholiaQ113779014MaRDI QIDQ5099100
Lyuben Lichev, Nicolas Fraiman, Dieter 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
randomized algorithmBoolean functionthresholdhitting probabilityAchlioptas processpower of choicerelevant variable
General topics of discrete mathematics in relation to computer science (68R01) Stochastic processes (60G99) Boolean functions (06E30) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Boolean functions (94D10)
Cites Work
- Unnamed Item
- Unnamed Item
- Achlioptas process phase transitions are continuous
- Birth control for giants
- Threshold functions
- Avoiding a giant component
- Delaying satisfiability for random 2SAT
- Creating Small Subgraphs in Achlioptas Processes With Growing Parameter
- A Power-of-Two-Choices Unbalanced Allocation Process
- Hamiltonicity thresholds in Achlioptas processes
- Random k -SAT and the power of two choices
- Memoryless Rules for Achlioptas Processes
- Balanced allocation on graphs
- Avoiding small subgraphs in Achlioptas processes
- Balanced Allocations
- Every monotone graph property has a sharp threshold
- Combinatorics in the exterior algebra and the Bollobás Two Families Theorem
- Semi‐random graph process
- Balanced Allocations: The Heavily Loaded Case
- Explosive Percolation in Random Networks
