A parity function $f_s:\{0,1\}^{n}\rightarrow\{0,1\}$, for some $s\in \{0,1\}^n$, is a function of the form $f_s(x) = x \cdot s$, where the inner product is taken modulo 2.

Show that $f_s$ is a balanced function for all $s$

We have $f_s(x) =\sum_i x_is_i \mod 2$. If $s \neq 0^n$, then there exist $i$ such that $s_i \neq 0$. So, for all $x$, $f_s(x) \neq f_s(x^i)$, where $x^i$ the string obtained from by inverting bit $i$. Hence $f_s$ is balanced.

I really don't understand the second from last sentence. Why this does this imply the function is balanced?


Let's say that the first bit of $s$ $s_0=1$ (the argument will be exactly the same for any bit, just for convenience).

You can split the space of inputs $x \in \{0,1\}^n$ in two halves: one half where $x_0 = 0$ and the other half where $x_0 = 1$. For each bitstring $x$ from the first half you'll have a bitstring $\tilde{x}$ from the second half which will be equal to $x$ in all bits except the first one, and will differ from $x$ in the first bit.

Now consider $f_s(x)$ and $f_s(\tilde{x})$; you'll have $f_s(x) = x_0s_0 + F$ and $f_s(\tilde{x}) = \tilde{x}_0s_0 + F$ ($F$ is the sum of all terms except the first one). You know that $x_0 = 0$ and $\tilde{x}_0 = 1$, so you'll have $F = f_s(x)$ and $f_s(\tilde{x}) = 1 + F$, so you're guaranteed that $f_s(x) \neq f_s(\tilde{x})$.

This way you can split all possible $x$ in $2^{n-1}$ pairs, and each of the pairs will have different values of $f_s$ - which means that exactly $2^{n-1}$ values are 0 and $2^{n-1}$ are 1, and the function is balanced.

  • $\begingroup$ Genius! Thanks! $\endgroup$
    – Trajan
    Jun 16 '20 at 21:03

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.