18 problems

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$,…

Let $f:X^n\to\\{0,1\\}$ be a Boolean function on a product probability space, and let $I_f$ be the sum of its variable influences. Dinur–Friedgut's conjecture. The Friedgut approxi…

Let $f:[0,1]^n\to\\{0,1\\}$ be a Boolean function, and let $I_f$ denote the sum of its variable influences. A function $g:[0,1]^n\to\\{0,1\\}$ depends on a set of variables if its…

Yao–Karp conjecture. The same lower bound holds for randomized decision tree complexity:

Let $D(f)$ denote the deterministic decision tree complexity of a Boolean function $f$, and let $R(f)$ denote its randomized decision tree complexity. Define … For the recursively…

Combinatorial-term conjecture. The full minimax rate should include this combinatorial term as an additive contribution, in addition to the smoothness term.

Assumption-free quarter-rate conjecture. The same conclusion of Theorem 1/4+ε for variance holds without those assumptions.

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…

Consider a diagram formed by vertical and horizontal cuts, where a diagram corresponds to a tree when it can be represented by the recursive subdivision associated with a decision…

Let $p=1$, let $\hat\imath$ be the CART split index at the root node, and let $a,b\in(0,1)$ with $a<b$. The data are ordered so that the root split threshold is…

In the setting of Boolean degree $d$ functions on Grassmann graphs and the constant-depth decision-tree conjecture, the depth of the decision tree is the quantity under considerati…

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…

Full-column-rank conjecture. The template matrix $B$ is of full column rank for any binary decision tree.

Let $S_n$ be the symmetric group, and let $fa S_n\to\{0,1\}$ be a Boolean function. Say that $f$ is $\epsilon$-close to degree $d$ if there exists a degree-$d$ function…

Let $L^{\star}(1,s)$ be the function of $s$ defined in the preceding analysis, for the fixed parameters appearing there. The function is symmetric around $1/2$. Monotonicity conjec…

Let $T$ be a decision tree computing a Boolean function $f$, and let ${\bf Cov}[T]$ be the covariance measure defined recursively on the tree. Let $\operatorname{Var}[f]$ denote th…

Let $G$ be a graph. An activity is strongly Tutte-descriptive if it is Tutte-descriptive and induces a partition … A decision tree $\Delta$ is the recursive edge-labeled structure…

Let $f$ be a Boolean function whose Fourier spectrum is sparse, meaning that it has only $s$ nonzero Fourier coefficients. A parity decision tree (abbreviated $\oplus$-DT) is a dec…