# Counting argument for LTF circuits

In Boolean circuit complexity, Shanon's counting argument shows that a random Boolean function on $$n$$-input bits requires a circuit of size $$\Omega(2^n/n)$$ to be computed by a circuit made of AND, OR and NOT gates. Is there a similar lower bound for random functions against LTF(Linear Threshold Function) circuits?

More precisely, is it known that a random Boolean function requires a super-polynomial-sized LTF circuit?

• Oh, I see. IIRC any linear threshold function in $s$ inputs can be written as $\sum_ia_ix_i>a$ where $a_i$ and $a$ are integers of magnitude $2^{O(s)}$, which means that the function can be specified using $O(s^2)$ bits. Thus, a LTF circuit of size $s$ can be described using $O(s^3)$ bits. Thus, there exist Boolean functions in $n$ variables that require LTF circuits of size $\Omega(2^{n/3})$. Dec 16, 2022 at 22:35
• Thanks! That answers my question. I believe the claim about the weights of LTFs follows from a paper of Goldman, Hastad and Razbarov. Dec 16, 2022 at 22:53
• They state it as Lemma 1, but cite it as an old result. However, the bound is roughly $s^{s/2}$ rather than $2^{O(s)}$, which, by the argument above, gives that a size $s$ LTF circuit can be represented by $O(s^3\log s)$ bits, and a random function requires circuit size $\Omega(2^{n/3}/n)$. But I think the source of the $s^{s/2}$ bound is basically Hadamard’s bound applied to bound coefficients of a hyperplane determined by an affinely independent set of points of $\{0,1\}^s$. If so, this can still be described with $O(s^2)$ bits, thus the $O(s^3)$ and $\Omega(2^{n/3})$ bounds should hold. Dec 17, 2022 at 11:02
• Yes, the bounds hold. I made it a proper answer. Dec 20, 2022 at 7:04

## 1 Answer

It is known that any LTF in $$n$$ variables can be expressed as $$\sum_ia_ix_i\ge b$$ where $$a_i$$ and $$b$$ are integers with $$|a_i|,|b|\le n^{O(n)}$$ (see e.g. Lemma 1 in Goldmann, Håstad, and Razborov, Majority gates vs. general weighted threshold gates, Computational Complexity 2 (1992), 277–300, where the bound is given as $$2^{-n}(n+1)^{(n+1)/2}$$). Thus, for an LTF circuit of size $$s$$, we can describe each gate using $$O(s^2\log s)$$ bits, and the whole circuit using $$O(s^3\log s)$$ bits. It follows by a counting argument that a random Boolean function in $$n$$ variables requires LTF circuit size $$\Omega(2^{n/3}/n)$$.

We can improve this to $$2^{n/3}$$ as follows. Let $$f\colon\{0,1\}^n\to\{0,1\}$$ be a LTF. The set $$C_f$$ of coefficients $$(\vec a,b)\in\mathbb R^{n+1}$$ such that $$\sum_ia_ix_i\ge b$$ computes $$f$$ is defined by a finite system of inequalities of the form $$L_j(\vec a,b)\ge0$$ or $$L_j(\vec a,b)<0$$, where each $$L_j$$ is a linear function with $$\{0,1\}$$ coefficients. Since $$C_f$$ is invariant by multiplication by a positive scalar, it remains nonempty if we strengthen each inequality $$L_j<0$$ to $$L_j\le-1$$. In this way, we obtain a feasible linear program, and by general properties of linear programs, there exists a set $$J$$ such that the affine space determined by the equalities $$L_j=0$$ or $$L_j=-1$$ (as appropriate) for $$j\in J$$ is a nonempty subset of $$C_f$$. We may assume these equalities are linearly independent, thus $$|J|\le n+1$$. Interpreting this in terms of the coefficients of the original LTF, we obtain:

Lemma: For any LTF $$f\colon\{0,1\}^n\to\{0,1\}$$, there exists a set $$X\subseteq\{0,1\}^n$$ such that $$|X|=n+1$$ and every LTF $$g$$ that agrees with $$f$$ on $$X$$ is identical to $$f$$.

(The $$n^{O(n)}$$ bound then also follows using Cramer’s rule and Hadamard’s determinant inequality, but we will not need this.)

It follows that $$f$$ can be described using $$(n+1)n+(n+1)=(n+1)^2$$ bits. Thus, a LTF circuit of size $$s$$ can be described using $$\sum_{t\le s}t^2\sim s^3/3 bits, and a random Boolean function in $$n$$ variables requires LTF circuits of size $$\ge2^{n/3}$$ with high probability.

The bound above assumes the size of the circuit is measured by the number of nodes. If we use the number of wires instead, a circuit with $$w$$ wires has $$s$$ nodes of fan-ins $$\{w_i:i such that $$\sum_iw_i=w$$; by the above, the gates can be described using $$\sum_i(w_i+1)^2\le(w+1)^2$$ bits, and the wiring with $$2w\log s\le2w\log w$$ bits, thus the whole circuit can be described using $$O(w^2)$$ bits. Consequently, a random Boolean function in $$n$$ variables requires LTF circuits with $$\Omega(2^{n/2})$$ wires.