ECCC-Report TR21-111https://eccc.weizmann.ac.il/report/2021/111Comments and Revisions published for TR21-111en-usWed, 15 Jun 2022 19:23:36 +0300
Revision 1
| Influence of a Set of Variables on a Boolean Function |
Aniruddha Biswas,
Palash Sarkar
https://eccc.weizmann.ac.il/report/2021/111#revision1The 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.Wed, 15 Jun 2022 19:23:36 +0300https://eccc.weizmann.ac.il/report/2021/111#revision1
Paper TR21-111
| Influence of a Set of Variables on a Boolean Function |
Aniruddha Biswas,
Palash Sarkar
https://eccc.weizmann.ac.il/report/2021/111The 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.
Sun, 25 Jul 2021 19:37:04 +0300https://eccc.weizmann.ac.il/report/2021/111