1
$\begingroup$

This paper by Maslov et al. uses that the probability of two $n$-bit Boolean functions $l(x)$ and $g(x)$ being equal is bound in terms of $\hat{g}_\text{max}$, the largest Fourier coefficient of $g(x)$, in the following way (between Eq. (4) and (5) of the Methods section at the end of the paper): \begin{equation} \Pr[l(x)=g(x)]\leq\frac{1}{2}(1+\hat{g}_{\text{max}}). \end{equation} Here, the binary Fourier transform of the Boolean function $g : \{0,1\}^n\mapsto\{0,1\}$ is defined as (with $x\cdot y$ the bitwise inner product between $n$-bit strings $x,y\in\{0,1\}^n$) \begin{equation} \hat{g}(y)=2^{-n}\sum_{x\in\{0,1\}^n}(-1)^{x\cdot y+g(x)}, \end{equation} and $\hat{g}_\text{max}$ is defined as \begin{equation} \hat{g}_\text{max}=\max_{y\in\{0,1\}^n}|\hat{g}(y)|. \end{equation} I've tried understanding this myself, as well as going over literature concerning the Boolean Fourier transform (as, for example, these texts by Ryan O'Donnell (1 and 2) and Ronald de Wolf), but I haven't been able to see why the inequality holds. I got as far as realizing that the Fourier transform of $g(x)$ allows for the following relations: \begin{equation} g(x)=\frac{1}{2}\bigg(1-\sum_{y\in\{0,1\}^n}\hat{g}(y)(-1)^{y\cdot x}\bigg)\leq\frac{1}{2}(1+2^n\hat{g}_\text{max}). \end{equation} This, however, does not seem to be particularly useful. Any nudge in the right direction would be hugely appreciated!

$\endgroup$

1 Answer 1

2
$\begingroup$

As the RHS is independent of $l(x)$, the statement should only be true if $l(x)$ lies in a restricted subset of Boolean functions. I cannot read the paper linked, but I suspect it is intended to restrict $l(x)$ to linear functions, i.e. $l(x)=l_y(x)=x\cdot y$.

In that case it is easy to show $$Pr\left[l_y(x)=g(x)\right] = \frac12 \left(1 + \hat{g}(y)\right)$$ and the result follows by taking the absolute value, then the triangle inequality, then the max over all $y$.

$\endgroup$
1
  • 1
    $\begingroup$ Thank you very much for your answer! You are completely right that they restrict $l(x)$ to linear functions: I now see the importance of that restriction. It then follows that $\hat{g}(y)=\mathbb{E}[(-1)^{x\cdot y + g(x)}]=\Pr[l_y(x)=g(x)]-\Pr[l_y(x)=g(x)+1]$. Given that $\Pr[l_y(x)=g(x)+1]=1-\Pr[l_y(x)=g(x)]$, we have $\Pr[l_y(x)=g(x)]=\frac{1}{2}(1+\hat{g}(y))$. $\endgroup$
    – Sebastian
    Jan 4, 2022 at 14:04

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.