Article ID Journal Published Year Pages File Type
4649364 Discrete Mathematics 2009 5 Pages PDF
Abstract

For a function f:{0,1}n→Rf:{0,1}n→R and an invertible linear transformation L∈GLn(2)L∈GLn(2), we consider the function Lf:{0,1}n→RLf:{0,1}n→R defined by Lf(x)=f(Lx)Lf(x)=f(Lx). We raise two conjectures: First, we conjecture that if ff is Boolean and monotone then I(Lf)≥I(f)I(Lf)≥I(f), where I(f)I(f) is the total influence of ff. Second, we conjecture that if both ff and L(f)L(f) are monotone, then f=L(f)f=L(f) (up to a permutation of the coordinates). We prove the second conjecture in the case where LL is upper triangular.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,