Lecture 2. Circuit model of computations

At the Lecture we continued discussing various properties of classical Boolean circuits. Any Boolean operation contains some number of bit at the input (fan-in) and at the output (fan-out). It is often natural to assume that all gates from a dictionary have a bounded input, since physically relevant operations on bits are usually local. On the other hand, since classical information is easy to copy, it is often convenient to assume that there is no bound on fan-out. If we accept this convention, and if the dictionary is universal, then any function can be realised in linear depth. Also, we have shown by counting argument that most Boolean functions require an exponential number of gates. Throughout the course, we will often be interested in the non-universal class of affine Boolean functions. Such functions are related to linear algebra over $\mathbb{Z}_2$ and are implementable by circuits from the dictionary $\{\mathrm{NOT},\mathrm{XOR}\}$. We can introduce the Walsh-Hadamard-Fourier transform over the space of Boolean functions. The Fourier transforms of linear Boolean functions are exactly $\delta$-functions. It is possible to decide languages by means of circuit families, and the complexity of a language is determined by the complexity of such families construction.