Random functions of low degree as a real polynomial

Is there a (reasonable) way to sample a uniformly random boolean function $f:\{0,1\}^n \to \{0,1\}$ whose degree as a real polynomial is at most $d$?

EDIT: Nisan and Szegedy have shown that a function of degree $d$ depends on at most $d2^d$ coordinates, so we may assume that $n \leq d2^d$. The problems as i see are the following: 1) On one hand if we pick a random boolean function on $d2^d$ coordinates, then its degree will be close to $d2^d$, much higher than $d$. 2) On the other hand, if we pick each coefficient of degree at most $d$ at random, then the function will not be boolean.

So the question is: is there a way to sample a low degree boolean function that avoids these two problems?

• Do you want the actual function to be the restriction of a real polynomial of degree $d$ to 0-1 inputs, or do you want it to be that $f(x) = 1$ iff $p(x) > 0$ for some real polynomial $p$ of degree at most $d$? Or something else? – Joshua Grochow Aug 23 '13 at 20:00
• @JoshuaGrochow I want a function whose Fourier expansion has degree $d$. That is your first option. – Igor Shinkar Aug 24 '13 at 4:38
• What is your model? Writing down the sampled function takes $2^n$ time, or $n^{O(d)}$ if you want to output the Fourier expansion. Is $d$ a fixed constant? – MCH Aug 24 '13 at 15:05
• I added some more details in the question. – Igor Shinkar Aug 24 '13 at 17:35
• @MCH If a function if of degree $d$ (with zero weight above level $d$), then it cannot depend on more than $d2^d$ coordinates. This is a result due to Nisan and Szegedy. Think about the special case of $d=1$. In this case we know that the function depends on (at most) 1 coordinate. – Igor Shinkar Aug 26 '13 at 4:22

Here's an algorithm that beats the trivial attempts.

The following is a known fact (Exercise 1.12 in O'Donnell's book) : If $$f:\{-1,1\}^n\to\{-1,1\}$$ is a Boolean function which has degree $$\le d$$ as a polynomial, then every Fourier coefficient of $$f$$, $$\hat{f}(S)$$ is an integer multiple of $$2^{-d}$$. Using Cauchy-Schwarz and Parseval one gets that there are at most $$4^d$$ nonzero Fourier coefficients and $$\sum_{S}{|\hat{f}(S)|}\le 2^{d}$$.

This suggests a sampling method -

1. Choose random non-negative integers $$a_S$$ for all sets $$S\subseteq[n]$$ of size at most $$d$$, which sum up to $$\le 4^d$$.
2. Let $$f(x) = \sum_{S}{\frac{a_S}{2^d} \chi_S(x)}$$.
3. Verify that $$f$$ is Boolean. If so, return $$f$$. Else, go back to $$1$$.

Note that for every degree $$\le d$$ polynomial $$f$$ exactly one choice of random integers in Step 1 will generate the polynomial $$f$$. The probability of getting a specific degree $$\le d$$ polynomial is $$1/\binom{\binom{n}{\le d}+4^d}{4^d} =1/O(n/d)^{d4^d}.$$ Hence, we need to repeat this process at most $$O(n/d)^{d4^d}$$ times, in expectation, before halting.

It remains to show how to perform step 3. One can define $$A = \bigcup\{S:a_S\neq 0\}$$. Check that $$|A| \le d 2^d$$ (which should hold by Nisan-Szegedy for every Boolean function) and then evaluate $$f$$ on all possible assignments to the variables in $$A$$. This can be done in time $$2^{d 2^d}$$. Gur and Tamuz offer a much faster randomized algorithm for this task, however since this part doesn't dominate the time complexity this is enough.

Overall the algorithm produces a random sample of a degree $$\le d$$ polynomial in time $$O(\frac{n}{d})^{d4^d}$$. Under the assumption that $$n \le d2^d$$ the time complexity is $$2^{O(d^2 4^d)}$$.

This is not a polynomial time sampling algorithm, although it is much faster then sampling a completely random function (in which case the probability of getting a specific degree $$\le d$$ polynomial is $$1/2^{2^n}$$).

• Nice! Actually this gives an algorithm that w.h.p. (w.r.t. $d$) outputs the maximal possible number of coordinates that low degree function can depend on. Just take $n = 10d2^{d}$ to be sufficiently large, sample many function, and for each function count the number of influential coordinates. Output the maximum you see. – Igor Shinkar Oct 29 '14 at 18:25