Linear transformations of monotone functions on the discrete cube (Q1043603)

From MaRDI portal
Revision as of 13:08, 11 July 2023 by Importer (talk | contribs) (‎Created a new Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Linear transformations of monotone functions on the discrete cube
scientific article

    Statements

    Linear transformations of monotone functions on the discrete cube (English)
    0 references
    0 references
    0 references
    9 December 2009
    0 references
    In the paper under review, the authors present two conjectures regarding Boolean functions \(f:\{0,1\}^{n}\rightarrow \{0,1\}\), invertible linear transformations \(L\in GL_{n}(2)\), and the ``total influence'' \(I(f)\), discussed by \textit{M. Ben Or}, \textit{N Linial} and \textit{M. Saks} [in: Combinatorics, Proc. 7th Hung. Colloq., Eger/Hung. 1987, Colloq. Math. Soc. János Bolyai 52, 75--112 (1988; Zbl 0675.90107)]. The first conjecture is that if \(f\) is monotone then \(I(f)\leq I(f\circ L)\) for every \(L\in GL_{n}(2)\). The second conjecture is that if \(f\) is monotone then the composition \(f\circ L\) can only be monotone if it coincides with \(f\) up to a permutation of the coordinates. The authors verify the second conjecture in the special case where \(f\) is upper triangular.
    0 references
    influences
    0 references
    Boolean functions
    0 references
    Fourier-Walsh expansion
    0 references
    discrete Fourier analysis
    0 references

    Identifiers