4 problems

Characterization of strongly Tutte-descriptive activities. For any graph $G$, an activity $\psi$ is strongly Tutte-descriptive if and only if there exists a decision tree $\Delta$…

Composition multiplicativity conjecture. For every $n,m\ge1$, there exists $k_0(n,m)\in\mathbb N$ such that, for every Boolean functions $f$ and $g$ on $n$ and $m$ bits, respective…

Let $J_q(n,k)$ be the Grassmann graph on the $k$-dimensional subspaces of an $n$-dimensional vector space over the finite field of order $q$. A Boolean degree $d$ function is a Boo…

A Boolean function is a function $f:\{0,1\}^n\to\{0,1\}$. Its decision-tree complexity $D(f)$ is the minimum number of input bits an adaptive algorithm must query to determine $f$,…