3
$\begingroup$

I am wondering how to use Mathematica to demonstrate some concepts in Analysis of Boolean functions, e.g.:

  • Influence
  • Noise stability
  • Noise operator
  • $L_q$-norm and $L_\infty$ norm of a boolean function

Any help would be appreciated.


All $2^{(2^2)}=16$ boolean functions $f: \{ -1,1 \}^2\rightarrow \{ -1, 1\}$ are:

$$ \left( \begin{array}{c} -1 \\ \frac{x_2 x_1}{2}+\frac{x_1}{2}+\frac{x_2}{2}-\frac{1}{2} \\ -\frac{1}{2} x_2 x_1+\frac{x_1}{2}-\frac{x_2}{2}-\frac{1}{2} \\ x_1 \\ -\frac{1}{2} x_2 x_1-\frac{x_1}{2}+\frac{x_2}{2}-\frac{1}{2} \\ x_2 \\ -x_1 x_2 \\ -\frac{1}{2} x_2 x_1+\frac{x_1}{2}+\frac{x_2}{2}+\frac{1}{2} \\ \frac{x_2 x_1}{2}-\frac{x_1}{2}-\frac{x_2}{2}-\frac{1}{2} \\ x_1 x_2 \\ -x_2 \\ \frac{x_2 x_1}{2}+\frac{x_1}{2}-\frac{x_2}{2}+\frac{1}{2} \\ -x_1 \\ \frac{x_2 x_1}{2}-\frac{x_1}{2}+\frac{x_2}{2}+\frac{1}{2} \\ -\frac{1}{2} x_2 x_1-\frac{x_1}{2}-\frac{x_2}{2}+\frac{1}{2} \\ 1 \\ \end{array} \right) $$

$\endgroup$

1 Answer 1

2
$\begingroup$

I don't find that, so I implemented some concepts by myself.

Any supplementation would be appreciated.


The number of boolean functions whose Fourier degree is exactly $d$ and inputBinaryWord length is $n$.

Here the Fourier degree of a boolean function $f:\{ -1,1 \}^n \rightarrow \{ -1,1 \}$ is its degree as a multilinear polynomial.

n = 2;
inputWords = Tuples[{-1, 1}, n];
outputResults = Tuples[{-1, 1}, 2^n];
expr = {Product[1/2 (1 + Subscript[a, i] Subscript[x, i]), {i, n}]}~
   Join~Array[{Subscript[a, #], {-1, 1}} &, n];
allIndicatorFunctions = Flatten[Table @@ expr];
allBooleanFunctions = 
  Table[Expand[fa . allIndicatorFunctions], {fa, outputResults}];
allBooleanFunctions // TableForm
polynomialDegree[expr_] := 
  Max[0, Max[Total@*First /@ CoefficientRules[expr]]];
(polynomialDegree /@ allBooleanFunctions) // Tally

The number of boolean functions $\{ -1, 1\}^{n} \rightarrow \{-1, 1 \}$ whose Fourier degree equals to $d$:

$$ \begin{array}{c|ccccccccccc} n\backslash d & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline 1 & 2 & 2 & - & - & - & - & - & - & - \\ 2 & 2 & 4 & 10 & - & - & - & - & - & - \\ 3 & 2 & 6 & 62 & 186 & - & - & - & - & - \\ 4 & 2 & 8 & 212 & 12648 & 52666 & - & - & - & - \\ \cdots & - & - & - & - & - & - & - & - & - \end{array} $$

The diagonal elements are the diagonal elements in the array are sequence A037267.

The $i$'th influence of a boolean function

$$ \operatorname{Inf}_i [f]=\mathrm{E}[(\frac{f-f^{\oplus i}}{2})^2]=\sum_{S \ni i} \hat{f}(S)^2 $$

Where $f^{\oplus i}$ denotes the output obtained by flipping the $i $-th bit of the input vector.

iThInfluenceOfFunctionf[original_, bitsNumber_, ithBit_] := 
 Module[{iThBitFlipped, expr}, 
  iThBitFlipped = 
   original /. {Subscript[x, ithBit] -> -Subscript[x, ithBit]};
  expr = {((original - iThBitFlipped)/2)^2}~Join~
    Array[{Subscript[x, #], {-1, 1}} &, bitsNumber];
  Table @@ (expr) // Flatten // Mean]

Table[iThInfluenceOfFunctionf[booleanFunction, n, 
    ithBit], {booleanFunction, allBooleanFunctions}, {ithBit, n}] // 
  Flatten // Tally

Total influence of $f$, namely, the average sensitivity

$$ \operatorname{Inf}[f]=\sum_{i=1}^n \operatorname{Inf}_i[f]=\sum_S|S| \hat{f}(S)^2 $$

The sensitivity of a boolean function $f$ at a given point is the number of coordinates $i$ such that if we flip the $i$'th coordinate, the value of the function changes. The average value of this quantity is exactly the total influence.

totalInfluenceOfFunctionf[f_, bitsNumber_] := 
  Sum[iThInfluenceOfFunctionf[f, bitsNumber, ithBit], {ithBit, 
    bitsNumber}];
totalInfluenceOfFunctionf[#, n] & /@ allBooleanFunctions

$\rho-$stable influence of a boolean function

$$ \operatorname{Stab}_\rho[f]=\mathrm{E}_{x ; y \sim N_\rho(x)}[f(x) f(y)]=\sum_{S \subseteq[n]} \rho^{|S|} \hat{f}(S)^2 $$

noiseStabilityOfFunctionf[f_, \[Rho]_] := 
 CoefficientRules[f] // 
   Map[(\[Rho]^Total[#[[1]]])*(#[[2]])^2 &, #] & // Total
noiseStabilityOfFunctionf[#, \[Rho]] & /@ allBooleanFunctions

The noise sensitivity of $f$ at $0\leq \delta\leq 1$

$$ \operatorname{NS}_{\delta}[f]=\frac{1}{2}-\frac{1}{2}\operatorname{Stab}_{1-2\delta}[f] $$

If $f$ is boolean, then this is the probability that the value of $f$ changes if we flip each coordinate with probability $\delta$, independently.

noiseSensitivityOfFuncitonf[f_, \[Delta]_ ] := 
 1/2 - 1/2*noiseStabilityOfFunctionf[f, 1 - 2 \[Delta]] // Expand
noiseSensitivityOfFuncitonf[#, \[Delta]] & /@ allBooleanFunctions

$L_q-$norm of a boolean function

$$ \|f\|_q=\sqrt[q]{\mathrm{E}\left[|f|^q\right]} . $$

LqNormOfFunctionf[f_, bitsNumber_, q_] := Module[{expr},
   expr = {Abs[f]^q}~Join~
     Array[{Subscript[x, #], {-1, 1}} &, bitsNumber];
   Table @@ expr // Flatten // Mean // (#^(1/q)) &];

Table[LqNormOfFunctionf[f, n, 2], {f, allBooleanFunctions}]

$L_{\infty}-$norm of a boolean function

$$ \|f\|_{\infty}=\max _{x \in\{-1,1\}^n}|f(x)| . $$

LInfinityNormOfFunctionf[f_, bitsNumber_] := 
 Module[{expr}, 
  expr = {Abs[f]}~Join~Array[{Subscript[x, #], {-1, 1}} &, bitsNumber];
  Max[Flatten[Table @@ expr]]]
LInfinityNormOfFunctionf[#, n] & /@ allBooleanFunctions
$\endgroup$

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.