13 problems

A Boolean function is a map $f:[?{0,1}^n\rightarrow\{0,1\}$. Its sensitivity is the maximum, over inputs, of the number of coordinates whose change alters the function value; its d…

Let $m$ be a positive integer, let $\varepsilon$ be an $m$-th primitive root of unity, and let $H(n,m)$ be the Hamming graph. Write $H_1,\dots,H_m$ for possibly empty induced subgr…

Let $m$ be a positive integer, let $\varepsilon$ be an $m$-th root of unity, and let $H(n,m)$ be the Hamming graph on $\mathcal U_m^{\,n}$. For each $k$, let $H_{\varepsilon^k}$ be…

Mean sensitivity equivalence conjecture. A topological dynamical system is mean $n$-sensitive if and only if it is $n$-sensitive in the mean.

Let $(X,T)$ be a minimal topological dynamical system, and let a mean sensitive tuple and a topological sequence entropy tuple be tuples of points of $X$ as defined in the paper. T…

Let $(X,T)$ be a minimal topological dynamical system, and let an $n$-tuple mean a tuple of points of $X$. A mean sensitive $n$-tuple, an IT $n$-tuple, and a sequence entropy $n$-t…

Sensitivity-weighted variable conjecture. For every Boolean function $f$,

E-system dichotomy conjecture. This dichotomy is not true for $E$-systems in general.

Let $f$ be a Boolean graph property on the ${n \choose 2}$ possible edges. A min-term graph property is a graph property of the type defined in Chakraborty's work, and $f$ is non-t…

Let $f$ be a Boolean function on $n$ variables. A function is weakly symmetric if all coordinates have the same influence, and it is non-constant if it is not constant. Turan's con…

Nisan and Szegedy's quadratic conjecture. The block sensitivity satisfies

Nisan and Szegedy's Sensitivity Conjecture. There exist constants $c$ and $k$ such that for every Boolean function $f$,

Aaronson's lattice variant. There exist constants $c$ and $k$ such that for every non-trivial coloring $C$,