Linear transformations of monotone functions on the discrete cube
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.
- Boolean functions with low average sensitivity depend on few coordinates
- Every monotone graph property has a sharp threshold
- scientific article; zbMATH DE number 5504150 (Why is no real title available?)
- scientific article; zbMATH DE number 3957109 (Why is no real title available?)
- scientific article; zbMATH DE number 4106654 (Why is no real title available?)
- Krawtchouk polynomials and universal bounds for codes and designs in Hamming spaces
- Monotone Boolean functions
- Noise sensitivity of Boolean functions and applications to percolation
This page was built for publication: Linear transformations of monotone functions on the discrete cube
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1043603)
