Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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<s^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<s\}$ 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.
