Lesson 2

Advanced Problems.

1. (20 points) Show that for any Boolean function \(f \colon \{0, 1\}^{n}\to \{0, 1\}\), there exists a polynomial \(P(x)\) with the property that \(P(x) \in \mathbb{Z}\) for any \(x \in \mathbb{Z}\) and \[f(x_{1}, \dotsc, x_{n}) = P\left((x_{n} … x_{1})_{2}\right) \bmod 2.\]
   Hint:

   Consider \(\binom{n}{k}\bmod 2\).