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?

  • 3
    $\begingroup$ 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? $\endgroup$ Commented Aug 23, 2013 at 20:00
  • 3
    $\begingroup$ @JoshuaGrochow I want a function whose Fourier expansion has degree $d$. That is your first option. $\endgroup$ Commented Aug 24, 2013 at 4:38
  • 1
    $\begingroup$ 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? $\endgroup$ Commented Aug 24, 2013 at 15:05
  • 3
    $\begingroup$ I added some more details in the question. $\endgroup$ Commented Aug 24, 2013 at 17:35
  • 1
    $\begingroup$ @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. $\endgroup$ Commented Aug 26, 2013 at 4:22

1 Answer 1


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}$).

  • $\begingroup$ 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. $\endgroup$ Commented Oct 29, 2014 at 18:25
  • $\begingroup$ It worth noting that this implies a pretty grim outlook for generating low-degree functions on more than ~10 bits. For example, functions of degree2 or less with 10 bits will require 200 quadrillion attempts. And that isn't what one would normally consider a "big" domain for boolean function. Are there any ideas or research on how to improve upon this? $\endgroup$
    – Paul
    Commented 2 days ago

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.