Influence of a Set of Variables on a Boolean Function

DOI10.1137/22M1503531MaRDI QIDQ6077985zbMATH OpenOpenAlexFDO

Authors Aniruddha Biswas, Palash Sarkar

Publication date 27 September 2023

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

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

zbMATH Keywords

auto-correlationbent functionsBoolean functionFourier transforminfluenceJuntaresilient functionsWalsh transform

Mathematics Subject Classification ID

Boolean functions (06E30) Fourier and Fourier-Stieltjes transforms on locally compact and other abelian groups (43A25) Boolean functions (94D10)

Abstract: The influence of a variable is an important concept in the analysis of Boolean functions. The more general notion of influence of a set of variables on a Boolean function has four separate definitions in the literature. In the present work, we introduce a new definition of influence of a set of variables which is based on the auto-correlation function and develop its basic theory. Among the new results that we obtain are generalisations of the Poincar'e inequality and the edge expansion property of the influence of a single variable. Further, we obtain new characterisations of resilient and bent functions using the notion of influence. We show that the previous definition of influence due to Fischer et. al. (2002) and Blais (2009) is half the value of the auto-correlation based influence that we introduce. Regarding the other prior notions of influence, we make a detailed study of these and show that each of these definitions do not satisfy one or more desirable properties that a notion of influence may be expected to satisfy.

Recommendations

• On the influences of variables on Boolean functions in product spaces
• The influence of variables in product spaces
• An upper bound for the relative influence of variables on Boolean functions
• Influences of monotone Boolean functions
• On influences of Boolean variables and their computation

Cites work

• A spectral characterization of correlation-immune combining functions
• Analysis of Boolean Functions
• Boolean functions for cryptography and coding theory
• Boolean functions: influence, threshold and noise
• Construction of Nonlinear Resilient Boolean Functions Using “Small” Affine Functions
• Correlation-immunity of nonlinear combining functions for cryptographic applications (Corresp.)
• Every monotone graph property has a sharp threshold
• scientific article; zbMATH DE number 177031 (Why is no real title available?)
• On ``bent functions
• Propagation characteristics and correlation-immunity of highly nonlinear Boolean functions
• Separation results for Boolean function classes
• Testing juntas
• Testing juntas nearly optimally
• The influence of large coalitions
• Tight bounds on the Fourier spectrum of \(\mathsf{AC}^0\)

Cited in

(2)

• Evaluation, Strength, and Relevance of Variables of Boolean Functions
• KKL theorem for the influence of a set of variables

This page was built for publication: Influence of a Set of Variables on a Boolean Function

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