Influence of a Set of Variables on a Boolean Function
Aniruddha Biswas, Palash Sarkar · SIAM Journal on Discrete Mathematics · 2023
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 generalizations of the Poincaré inequality and the edge expansion property of the influence of a single variable. Further, we obtain new characterizations of resilient and bent functions using the notion of influence. We show that the previous definition of influence due to Fischer et al. [ Proceedings of the 43 rd Symposium on Foundations of Computer Science (FOCS 2002 ), Vancouver, BC, Canada, IEEE Computer Society, 2002, pp. 103–112] and Blais [ Proceedings of the 41 st Annual ACM Symposium on Theory of Computing, STOC 2009, M. Mitzenmacher, ed., Bethesda, MD, ACM, 2009, pp. 151–158] 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 does not satisfy one or more desirable properties that a notion of influence may be expected to satisfy.