3 problems

Kush–Rossman's conjecture. The exponent $\frac{1}{3}\log_{\varphi} k\approx 0.49\log_2 k$ is optimal: no formulas of the relevant type and depth $O(\log k)$ can solve…

Let $G$ be a pattern graph. For each positive integer $n$, let $\mathrm{SUB}(G)$ denote the Boolean function on inputs encoding an $n$-vertex host graph $H$ whose vertices are colo…

Let $a_0=2-1$ and, for $n\geq 0$, let … Consider formula encodings whose gates are restricted to \{+,\times,\text{^}\} and whose inputs are restricted to $\{-1,1\}$. The asymptot…