Loading Web-Font TeX/Math/Italic
| 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.