When are sequences of Boolean functions tame?

DOI10.1214/21-ECP438zbMATH Open1487.60069arXiv2012.01970OpenAlexW4205934004MaRDI QIDQ2078232FDOQ2078232

Authors: Malin Palö Forsström 

Publication date: 28 February 2022

Published in: Electronic Communications in Probability (Search for Journal in Brave)

Abstract: In cite{js2006}, Jonasson and Steif conjectured that no non-degenerate sequence of transitive Boolean functions $(f_n{)}_{ngeq1}$ with $li{m}_{noinfty}I(f_n)=infty$ could be tame (with respect to some $(p_n{)}_{ngeq1}$). In a companion paper cite{f}, the author showed that this conjecture in its full generality is false, by providing a counter-example for the case when, at the same time, $li{m}_{noinfty}n{p}_n=infty$ and $li{m}_{noinfty}{n}^{a}lpha{p}_n=0$ for some $alphain(0,1).$ In this paper we show that with slightly different assumptions, the conclusion of the conjecture holds when the sequence $(p_n{)}_{ngeq1}$ is bounded away from zero and one.

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

Recommendations

• A tame sequence of transitive Boolean functions
• Denseness of volatile and nonvolatile sequences of functions
• Volatility of Boolean functions
• Pivotality versus noise stability for monotone transitive functions
• Limits of Boolean functions on \(\mathbb{F}_p^n\)

zbMATH Keywords

tameBoolean functions

Mathematics Subject Classification ID

Functional limit theorems; invariance principles (60F17) Combinatorial probability (60C05) Continuous-time Markov processes on discrete state spaces (60J27) Boolean functions (94D10)

Cites Work

• Analysis of Boolean Functions
• The influence of variables in product spaces
• Every monotone graph property has a sharp threshold
• Noise sensitivity of Boolean functions and applications to percolation
• Noise stability of functions with low influences: invariance and optimality
• Volatility of Boolean functions
• Noise Sensitivity of Boolean Functions and Percolation
• How much are increasing sets positively correlated?
• Quantitative relation between noise sensitivity and influences
• On quantitative noise stability and influences for discrete and continuous models
• Denseness of volatile and nonvolatile sequences of functions
• A tame sequence of transitive Boolean functions
• Pivotality versus noise stability for monotone transitive functions
• Concentration on the Boolean hypercube via pathwise stochastic analysis

Cited In (3)

• Volatility of Boolean functions
• Scaling limits for the threshold window: when does a monotone Boolean function flip its outcome?
• A tame sequence of transitive Boolean functions

This page was built for publication: When are sequences of Boolean functions tame?

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