<p>Here's an algorithm that beats the trivial attempts.</p>

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

<p>This suggests a sampling method - </p>

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

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

<p>It remains to show how to perform step 3. One can define <span class="math-container">$A = \bigcup\{S:a_S\neq 0\}$</span>. Check that <span class="math-container">$|A| \le d 2^d$</span> (which should hold by Nisan-Szegedy for every Boolean function) and then evaluate <span class="math-container">$f$</span> on all possible assignments to the variables in <span class="math-container">$A$</span>. This can be done in time <span class="math-container">$2^{d 2^d}$</span>.
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.</p>

<p>Overall the algorithm produces a random sample of a degree <span class="math-container">$\le d$</span> polynomial in time <span class="math-container">$O(\frac{n}{d})^{d4^d}$</span>.
Under the assumption that <span class="math-container">$n \le d2^d$</span> the time complexity is <span class="math-container">$2^{O(d^2 4^d)}$</span>.</p>

<p>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 <span class="math-container">$\le d$</span> polynomial is <span class="math-container">$1/2^{2^n}$</span>).</p>

CC BY-SA 3.0
2014-10-29T18:25:18.820Z
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
CC BY-SA 4.0
2024-06-19T14:04:57.970Z
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?
Paul
CC BY-SA 4.0
2014-10-27T19:43:15.633Z
2018-10-30T05:54:17.697Z
2018-10-30T05:54:17.697Z
Avishay Tal
<p>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$?</p>

<p>EDIT: <a href="http://link.springer.com/article/10.1007%2FBF01263419">Nisan and Szegedy</a> 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.</p>

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

CC BY-SA 3.0
2013-08-23T20:00:58.650Z
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
CC BY-SA 3.0
2013-08-24T04:38:36.417Z
@JoshuaGrochow I want a function whose Fourier expansion has degree $d$. That is your first option.
Igor Shinkar
CC BY-SA 3.0
2013-08-24T15:05:14.533Z
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
CC BY-SA 3.0
2013-08-24T17:35:18.377Z
I added some more details in the question.
Igor Shinkar
CC BY-SA 3.0
2013-08-26T00:22:34.930Z
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
CC BY-SA 3.0
2013-08-26T04:22:10.810Z
@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
CC BY-SA 4.0
2022-02-26T23:50:43.707Z
@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
<randomness><boolean-functions><bounded-degree>
Random functions of low degree as a real polynomial
Igor Shinkar
# Random functions of low degree as a real polynomial

(Asked by: username_0 on 2013-08-23)

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](http://link.springer.com/article/10.1007%2FBF01263419) 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?

**Tags:** randomness, boolean-functions, bounded-degree

> **Comments:**
> **username_1**: 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?  
> **username_0**: @JoshuaGrochow I want a function whose Fourier expansion has degree $d$. That is your first option.  
> **username_2**: 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?  
> **username_0**: I added some more details in the question.  
> **username_2**: 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.  
> **username_0**: @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.  
> **username_3**: @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$.  

---

## 1 answers

### Answer by username_4 on 2014-10-27. Score: 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}$).

> **Comments:**
> **username_0**: 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.  
> **username_5**: 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?  

---

