Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649364 | Discrete Mathematics | 2009 | 5 Pages |
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
Nathan Keller, Haran Pilpel,