Depth separation with explicit semi-algebraic crossing budgets

A computational block with two gates $\rho (z)$, $\rho (z-1\mathrm{/}2)$ followed by the gate $\rho (2u-4v)$ computes $h$. Compose $q$ blocks, identifying repeated parameter slots. Only the coordinate-selection vector of length $d$ and the four scalar slots $0,-1\mathrm{/}2,2,-4$ are needed: the first vector supplies coefficient $1$ for the selected coordinate and coefficient $0$ for the others, and its selected coefficient $1$ may also supply the fixed unit coefficient in subsequent blocks. There are $3q$ gates and $2q$ computational layers. Appending an affine identity produces the stated conversion. On the cube the output is the tent iterate in [F1].

Fix all coordinates except $x_1=z$, and consider any comparator with actual nonempty layer widths $m_1,\dots ,m_{\mathrm{\ell }}$ and $\mathrm{\ell }\le k$, ${\sum }_i{m}_i\le m$. Maintain one common partition of the line into open intervals on which all gates through layer $i$ are polynomials of degree at most ${\beta }^i$. Initially there is one interval and input coordinates are affine. In one previous interval, each of the at most $t{m}_i$ gate predicates at layer $i$ is a polynomial of degree at most $\alpha {\beta }^{i-1}$ after substitution, hence introduces at most that many roots unless identically zero, in which case its test is constant. Thus the new common partition has at most $1+t{m}_i\alpha {\beta }^{i-1}$ pieces per old piece. On each piece all indicators are constant, and the gate output is a polynomial of degree at most ${\beta }^i$. Skip edges cause no change: earlier outputs already have polynomial degree at most ${\beta }^{i-1}$ on this common partition.

It follows that the threshold classifier $1[g(z)\ge 1\mathrm{/}2]$ is constant on at most $C=(1+{\beta }^{\mathrm{\ell }}){\prod }_{i=1}^{\mathrm{\ell }}(1+t{m}_i\alpha {\beta }^{i-1})$ open intervals. Identically zero threshold polynomials contribute no roots. Since every factor's nonconstant term is at least one, $C\le 2(2t\alpha {)}^{\mathrm{\ell }}{\beta }^{\mathrm{\ell }(\mathrm{\ell }+1)\mathrm{/}2}{\prod }_i{m}_i\le 2(2t\alpha m\mathrm{/}\mathrm{\ell }{)}^{\mathrm{\ell }}{\beta }^{\mathrm{\ell }(\mathrm{\ell }+1)\mathrm{/}2}\le B$, where the penultimate inequality is AM–GM. The same partition argument applies for every fixed offset of the remaining coordinates.

Put $T=2^q$. By [F1], the target threshold classifier alternates on $N=T+1$ intervals in $[0,1]$. Its two end intervals have length $1\mathrm{/}(2T)$ and each of the others length $1\mathrm{/}T$. The integral of $\mathrm{\mid }f-1\mathrm{/}2\mathrm{\mid }$ is $1\mathrm{/}(8T)$ on each end interval and $1\mathrm{/}(4T)$ on each other interval. A comparator classifier with at most $C$ intervals has at most $C-1$ internal boundaries. Discard target intervals containing such a boundary. At most $C-1$ intervals are discarded; in each of the at most $C$ remaining runs the alternating target labels disagree with the constant comparator on at least half the run length minus $1\mathrm{/}2$. Hence at least $(N-2C)\mathrm{/}2$ target intervals disagree throughout, whenever this quantity is positive. Their contribution gives ${\int }_0^1\mathrm{\mid }f-g\mathrm{\mid }dz\ge \max \{0,(N-2C)\mathrm{/}(16T)\}$. Endpoint equalities have no effect on the integral. Integrating in the other coordinates gives the displayed bound and its $B\le T\mathrm{/}4$ consequence.

Write $s=t\alpha \beta$. For $\mathrm{\ell }=1$, the bound in step 2.1 is $4sm$. For $\mathrm{\ell }\ge 2$, use $(2\mathrm{/}\mathrm{\ell }{)}^{\mathrm{\ell }}\le 1$, $\mathrm{\ell }(\mathrm{\ell }+1)\mathrm{/}2\le {\mathrm{\ell }}^2$, and $\mathrm{\ell }\le {\mathrm{\ell }}^2$ to bound it by $2(sm{)}^{{\mathrm{\ell }}^2}$. Therefore $B\le 4(sm{)}^{k^2}$. If $m\le 2^{k\mathrm{/}s}$ and $s{2}^{k\mathrm{/}s}\le 2^k$, then $B\le 2^{k^3+2}=T\mathrm{/}4$. For $s=1$ the condition is equality; for fixed $s>1$ it is equivalent to $k\ge s{\log }_2(s)\mathrm{/}(s-1)$, so it eventually holds. This proves the exponential-budget assertion with all its indicated parameter cases.

Remove any unary branches and branches whose two outcomes compute the same subtree function, replacing them by their sole or common continuation; these reductions preserve the represented function and never increase the node count. A decision tree is then full binary: every internal branch has exactly two children. If it has $I$ internal nodes and $J$ leaves, its edge count is both $2I$ and $I+J-1$, so $J=I+1$ and $r=2I+1$. Consequently a full binary decision tree with at most $r$ total nodes has at most $(r-1)\mathrm{/}2$ internal branch nodes. On a fixed line each nonconstant affine test has at most one zero. A sum of at most $t$ such trees, with $r\le 2^{A\mathrm{/}t}$ and $A=k^3$, is constant away from at most $t(2^{A\mathrm{/}t}-1)\mathrm{/}2$ thresholds. Convexity of $u\mapsto 2^u$ yields $t(2^{A\mathrm{/}t}-1)\le 2^A-1$ for $t\ge 1$. Thus its threshold classifier has at most $(2^A+1)\mathrm{/}2\le 2^{A+2}=T\mathrm{/}4$ intervals. Step 3.1 proves the tree assertion. Finally at $k=d=t=\alpha =1$, the target $h^5$ is $32$-Lipschitz; its degree-$2^{22}$ Bernstein polynomial has uniform error at most $32\mathrm{/}(2\sqrt{2^{22}})=1\mathrm{/}128$ by [F2]. This polynomial is one $(1,1,2^{22})$ gate, allowed by the node budget $2^{1\mathrm{/}{2}^{22}}>1$, so the parameter restriction cannot be omitted.