Resolvable Fourier Degree and Minimax Estimation on theBoolean Hypercube

We study high-dimensional nonparametric regression on the Boolean hypercube $\{0,1{\}}^d$, from a sample of size $n$, under a Fourier–Sobolev budget, i.e., a bound $B$ on the total quadratic influence of the regression function. The central object is the resolvable Fourier degree $D^{\ast }(d,n)$, defined as the largest interaction order $D$ such that the dimension of the degree-$D$ Fourier–Walsh space does not exceed $n$. We prove that the minimax risk over Fourier–Sobolev ellipsoids is of order $B\mathrm{/}{D}^{\ast }(d,n)$: estimation is possible up to the statistically visible interaction order, and the budget controls the residual mass carried by higher-order interactions. We then study monotone regression under the same budget. For monotone functions supported on a known set of $s$ coordinates, with $s$ of order $\log n$, we obtain a matching minimax rate of order $B\mathrm{/}s$. Finally, we consider an unknown-support model in which the function is monotone and depends on at most $s$ coordinates; its minimax risk is governed by the intrinsic dimension $s$ together with the logarithmic cost of selecting the active support.