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^*(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/D^*(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/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.