Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR21-111 | 15th June 2022 19:23

Influence of a Set of Variables on a Boolean Function

RSS-Feed




Revision #1
Authors: Aniruddha Biswas, Palash Sarkar
Accepted on: 15th June 2022 19:23
Downloads: 21
Keywords: 


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.



Changes to previous version:

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.


Paper:

TR21-111 | 19th July 2021 11:14

Influence of a Set of Variables on a Boolean Function





TR21-111
Authors: Aniruddha Biswas, Palash Sarkar
Publication: 25th July 2021 19:37
Downloads: 290
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint