<p>It is known that any LTF in <span class="math-container">$n$</span> variables can be expressed as <span class="math-container">$\sum_ia_ix_i\ge b$</span> where <span class="math-container">$a_i$</span> and <span class="math-container">$b$</span> are integers with <span class="math-container">$|a_i|,|b|\le n^{O(n)}$</span> (see e.g. Lemma 1 in Goldmann, Håstad, and Razborov, <em>Majority gates vs. general weighted threshold gates</em>, Computational Complexity 2 (1992), 277–300, where the bound is given as <span class="math-container">$2^{-n}(n+1)^{(n+1)/2}$</span>). Thus, for an LTF circuit of size <span class="math-container">$s$</span>, we can describe each gate using <span class="math-container">$O(s^2\log s)$</span> bits, and the whole circuit using <span class="math-container">$O(s^3\log s)$</span> bits. It follows by a counting argument that a random Boolean function in <span class="math-container">$n$</span> variables requires LTF circuit size <span class="math-container">$\Omega(2^{n/3}/n)$</span>.</p>
<p>We can improve this to <span class="math-container">$2^{n/3}$</span> as follows. Let <span class="math-container">$f\colon\{0,1\}^n\to\{0,1\}$</span> be a LTF. The set <span class="math-container">$C_f$</span> of coefficients <span class="math-container">$(\vec a,b)\in\mathbb R^{n+1}$</span> such that <span class="math-container">$\sum_ia_ix_i\ge b$</span> computes <span class="math-container">$f$</span> is defined by a finite system of inequalities of the form <span class="math-container">$L_j(\vec a,b)\ge0$</span> or <span class="math-container">$L_j(\vec a,b)&lt;0$</span>, where each <span class="math-container">$L_j$</span> is a linear function with <span class="math-container">$\{0,1\}$</span> coefficients. Since <span class="math-container">$C_f$</span> is invariant by multiplication by a positive scalar, it remains nonempty if we strengthen each inequality <span class="math-container">$L_j&lt;0$</span> to <span class="math-container">$L_j\le-1$</span>. In this way, we obtain a feasible linear program, and by general properties of linear programs, there exists a set <span class="math-container">$J$</span> such that the affine space determined by the equalities <span class="math-container">$L_j=0$</span> or <span class="math-container">$L_j=-1$</span> (as appropriate) for <span class="math-container">$j\in J$</span> is a nonempty subset of <span class="math-container">$C_f$</span>. We may assume these equalities are linearly independent, thus <span class="math-container">$|J|\le n+1$</span>. Interpreting this in terms of the coefficients of the original LTF, we obtain:</p>
<blockquote>
<p><strong>Lemma:</strong> For any LTF <span class="math-container">$f\colon\{0,1\}^n\to\{0,1\}$</span>, there exists a set <span class="math-container">$X\subseteq\{0,1\}^n$</span> such that <span class="math-container">$|X|=n+1$</span> and every LTF <span class="math-container">$g$</span> that agrees with <span class="math-container">$f$</span> on <span class="math-container">$X$</span> is identical to <span class="math-container">$f$</span>.</p>
</blockquote>
<p>(The <span class="math-container">$n^{O(n)}$</span> bound then also follows using Cramer’s rule and Hadamard’s determinant inequality, but we will not need this.)</p>
<p>It follows that <span class="math-container">$f$</span> can be described using <span class="math-container">$(n+1)n+(n+1)=(n+1)^2$</span> bits. Thus, a LTF circuit of size <span class="math-container">$s$</span> can be described using <span class="math-container">$\sum_{t\le s}t^2\sim s^3/3&lt;s^3$</span> bits, and a random Boolean function in <span class="math-container">$n$</span> variables requires LTF circuits of size <span class="math-container">$\ge2^{n/3}$</span> with high probability.</p>
<p>The bound above assumes the size of the circuit is measured by the number of <em>nodes</em>. If we use the number of <em>wires</em> instead, a circuit with <span class="math-container">$w$</span> wires has <span class="math-container">$s$</span> nodes of fan-ins <span class="math-container">$\{w_i:i&lt;s\}$</span> such that <span class="math-container">$\sum_iw_i=w$</span>; by the above, the gates can be described using <span class="math-container">$\sum_i(w_i+1)^2\le(w+1)^2$</span> bits, and the wiring with <span class="math-container">$2w\log s\le2w\log w$</span> bits, thus the whole circuit can be described using <span class="math-container">$O(w^2)$</span> bits. Consequently, a random Boolean function in <span class="math-container">$n$</span> variables requires LTF circuits with <span class="math-container">$\Omega(2^{n/2})$</span> wires.</p>

CC BY-SA 4.0
2022-12-19T11:21:02.443Z
2022-12-19T14:14:28.897Z
2022-12-19T14:14:28.897Z
Emil Jeřábek
<p>In Boolean circuit complexity, Shanon's counting argument shows that a random Boolean function on <span class="math-container">$n$</span>-input bits requires a circuit of size <span class="math-container">$\Omega(2^n/n)$</span> 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?</p>
<p>More precisely, is it known that a random Boolean function requires a super-polynomial-sized LTF circuit?</p>

CC BY-SA 4.0
2022-12-16T22:53:37.987Z
Thanks! That answers my question. I believe the claim about the weights of LTFs follows from a paper of Goldman, Hastad and Razbarov.
Tulasi
<cc.complexity-theory><circuit-complexity><lower-bounds><boolean-functions>
Counting argument for LTF circuits
Tulasi
# Counting argument for LTF circuits

(Asked by: username_0 on 2022-12-16)

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?

**Tags:** cc.complexity-theory, circuit-complexity, lower-bounds, boolean-functions

> **Comments:**
> **username_0**: Thanks! That answers my question. I believe the claim about the weights of LTFs follows from a paper of Goldman, Hastad and Razbarov.  

---

## 1 answers

### Answer by username_1 on 2022-12-19. Score: 3 | Accepted 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.


---

