21
$\begingroup$

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?

$\endgroup$
  • 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$ – Joshua Grochow Aug 23 '13 at 20:00
  • 3
    $\begingroup$ @JoshuaGrochow I want a function whose Fourier expansion has degree $d$. That is your first option. $\endgroup$ – Igor Shinkar Aug 24 '13 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$ – MCH Aug 24 '13 at 15:05
  • 3
    $\begingroup$ I added some more details in the question. $\endgroup$ – Igor Shinkar Aug 24 '13 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$ – Igor Shinkar Aug 26 '13 at 4:22
11
$\begingroup$

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

$\endgroup$
  • $\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$ – Igor Shinkar Oct 29 '14 at 18:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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