2
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ 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})$. $\endgroup$ Dec 16, 2022 at 22:35
  • $\begingroup$ Thanks! That answers my question. I believe the claim about the weights of LTFs follows from a paper of Goldman, Hastad and Razbarov. $\endgroup$
    – Tulasi
    Dec 16, 2022 at 22:53
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 17, 2022 at 11:02
  • $\begingroup$ Yes, the bounds hold. I made it a proper answer. $\endgroup$ Dec 20, 2022 at 7:04

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.