Linear transformations of monotone functions on the discrete cube |
| |
Authors: | Nathan Keller Haran Pilpel |
| |
Institution: | Einstein Institute of Mathematics, Hebrew University, Jerusalem 91904, Israel |
| |
Abstract: | For a function f:{0,1}n→R and an invertible linear transformation L∈GLn(2), we consider the function Lf:{0,1}n→R defined by Lf(x)=f(Lx). We raise two conjectures: First, we conjecture that if f is Boolean and monotone then I(Lf)≥I(f), where I(f) is the total influence of f. Second, we conjecture that if both f and L(f) are monotone, then f=L(f) (up to a permutation of the coordinates). We prove the second conjecture in the case where L is upper triangular. |
| |
Keywords: | Influences Boolean functions Fourier-Walsh expansion Discrete Fourier analysis |
本文献已被 ScienceDirect 等数据库收录! |
|