I am reading Alon et al.'s paper Linear Circuits over $GF(2)$ and I am having trouble seeing the counting argument showing that most matrices need a circuit of size $\Omega(n^2/\log n)$. This result is also mentioned in Chazelle's book at the start of chapter 6. He gives the following hint: "Compare the number of possible sequences mod 2 and the number of matrices." and I am not really sure how to use it.

I tried to reformulate a slightly weaker statement but could not prove it. Let us have a circuit with $x_1, \dots, x_n$ as inputs and each gate computes $g_1 \pm g_2$ where the $g_i$'s are two previously computed gates. The circuit computes $Ax$ if there are $n$ nodes with values $Ax_i$ for any $x \in \mathbb{R}^n$. The size of the circuit is the number of edges and the complexity of $A$ is the size of the smallest circuit computing $A$. The proposition I want to show is that most matrices of this form have complexity in $\Omega(n^2/\log n)$.

Here is my attempt at a counting argument. We count the number of circuits: If we order the gates topologically, we see that the gate at step $k$ needs to choose 2 gates $g_1$ and $g_2$ from the ones previously computed and 1 from 3 ways to combine them ($g_1 + g_2$, $g_1 -g_2$, $g_2-g_1$, this yields $3\binom{k-1}{2}$ possibilities. We can bound this by above with $\frac{3k^2}{2}$. Now, if a circuit has size $s$, then there is going to be that much choice for each $k \in \{n+1, \dots, s\}$ and the product of all these terms is bounded above by $\frac{3^s}{2^s}(s!)^2 \leq \frac{3^s}{2^s}\left(\frac{s^s}{2^s}\right)^2$. Putting $s = n^2/\log n$ yields at most $\left(\frac{3n^4}{8\log^2n}\right)^{n^2/\log n}$ possible circuits, but we can write the number of matrices as $2^{n^2} = n^{n^2/\log n}$, and we clearly see that this is smaller than the number of circuits we computed before. I know that I am clearly over counting because some circuits might compute the same matrices and I use non-tight bounds, but I don't see the actual argument that gives this result.

Thanks for any help.

  • 1
    $\begingroup$ You are making the counting unnecessarily complicated, but anyway, take $s=\frac14n^2/\log n$ in the final step. $\endgroup$ – Emil Jeřábek Nov 16 '18 at 21:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.