July 29, 2021

SpywareNews.com

Dedicated Forum to help removing adware, malware, spyware, ransomware, trojans, viruses and more!

Influence of a Set of Variables on a Boolean Function. (arXiv:2107.08676v1 [cs.IT])

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.