Influence of a Set of Variables on a Boolean Function
Copyright policy )Influence of a Set of Variables on a Boolean Function
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é 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.
FOS: Computer and information sciences, influence, Computer Science - Cryptography and Security, bent functions, Computer Science - Information Theory, Information Theory (cs.IT), Walsh transform, Computational Complexity (cs.CC), auto-correlation, Junta, Computer Science - Computational Complexity, Fourier and Fourier-Stieltjes transforms on locally compact and other abelian groups, Boolean function, Fourier transform, resilient functions, Boolean functions, Cryptography and Security (cs.CR)
FOS: Computer and information sciences, influence, Computer Science - Cryptography and Security, bent functions, Computer Science - Information Theory, Information Theory (cs.IT), Walsh transform, Computational Complexity (cs.CC), auto-correlation, Junta, Computer Science - Computational Complexity, Fourier and Fourier-Stieltjes transforms on locally compact and other abelian groups, Boolean function, Fourier transform, resilient functions, Boolean functions, Cryptography and Security (cs.CR)
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).1 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!