Back to blog

Sensitivity Conjecture

For any $n\in\N$ and $f:\bit^n\rightarrow\bit$, $s(f)\leq DDT(f)$.

Does there exist a polynomial $p$ such that for any $n\in\N$ and $f:\bit^n\rightarrow\bit$, $DDT(f)\leq p(s(f))$?

Does there exist a polynomial $p$ such that for any $n\in\N$ and $f:\bit^n\rightarrow\bit$, $bs(f)\leq p(s(f))$?