22

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?

Igor Shinkar
  • 1,927
  • 11
  • 21
  • 3
    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
  • 3
    @JoshuaGrochow I want a function whose Fourier expansion has degree $d$. That is your first option. – Igor Shinkar Aug 24 '13 at 04:38
  • 1
    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? – Mahdi Cheraghchi Aug 24 '13 at 15:05
  • 3
    I added some more details in the question. – Igor Shinkar Aug 24 '13 at 17:35
  • I think the $d2^d$ bound is an approximation; the function may depend on all variables but it close to one that depends on $d 2^d$ variables. So it's not clear whether the upper bound assumption on $n$ is wlog. Unless I'm missing something. – Mahdi Cheraghchi Aug 26 '13 at 00:22
  • 1
    @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 04:22
  • @MahdiCheraghchi Note this is not about "mod 2" arithmetic. So for instance the XOR function cannot be represented as $x+y$, but it can be represented as $x+y-xy$. – Bjørn Kjos-Hanssen Feb 26 '22 at 23:50

1 Answers1

12

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

Bjørn Kjos-Hanssen
  • 4,485
  • 2
  • 25
  • 40
Avishay Tal
  • 363
  • 2
  • 8
  • 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