Revision #2 Authors: Aniruddha Biswas, Palash Sarkar

Accepted on: 14th February 2023 09:10

Downloads: 240

Keywords:

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.

We have included a new result (Theorem 3) on the spectral concentration bound of Boolean functions.

Revision #1 Authors: Aniruddha Biswas, Palash Sarkar

Accepted on: 15th June 2022 19:23

Downloads: 237

Keywords:

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.

Some new results has been introduced such as generalisations of the Poincar\'{e} inequality, the edge expansion property, new characterisations of resilient and bent functions using the notion of influence.

TR21-111 Authors: Aniruddha Biswas, Palash Sarkar

Publication: 25th July 2021 19:37

Downloads: 532

Keywords:

The influence of a set of variables on a Boolean function has three separate definitions in the literature, the first due to Ben-Or and Linial (1989), the second due to Fischer et al. (2002) and Blais (2009) and the third due to Tal (2017). The goal of the present work is to carry out a comprehensive study of the notion of influence of a set of variables on a Boolean function. To this end, we introduce a definition of this notion using the auto-correlation function. A modification of the definition leads to the notion of pseudo-influence. Somewhat surprisingly, it turns out that the auto-correlation based definition of influence is equivalent to the definition introduced by Fischer et al. (2002) and Blais (2009) and the notion of pseudo-influence is equivalent to the definition of influence considered by Tal (2017). Extensive analysis of influence and pseduo-influence as well as the Ben-Or and Linial notion of influence is carried out and the relations between these notions are established.