| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

4. The sensitivity theorem

The sensitivity conjecture was resolved in [MR4024566]. We look for more proofs and extensions.

    1. The sensitivity theorem


      Add remark

      Problem 4.1.

      The sensitivity theorem says that for all $n\ge 1$ and all Boolean function $f:\{-1,1\}^n\to \{-1,1\}$, we have \begin{equation*} s(f)\ge \sqrt{\deg (f)}. \end{equation*} More proofs of this result? Is it possible to formulate a reasonable problem for real-valued functions $f:\{-1,1\}^n\to \mathbb{R}$?

          Cite this as: AimPL: Analysis on the hypercube with applications to quantum computing, available at http://aimpl.org/hypercubequantum.