<p>It is actually possible to make use of random restrictions to prove lower bounds for threshold circuits.</p>

<p>In particular in the paper <a href="http://dx.doi.org/10.1137/S0097539792282965">Size-Depth Tradeoffs for Threshold Circuits</a>, Impagliazzo, Paturi, and Saks use random restrictions to prove a superliner lower bound (on the number of wires) for constant depth threshold circuits computing the parity function.</p>

<p>With regards to proving superpolynomial lower bounds for $\mathsf{TC}^0$
 circuits then yes, the natural proof concept is of relevance since there are <a href="http://dx.doi.org/10.1145/972639.972643">constructions</a> of pseudo-random function generators in $\mathsf{TC}^0$.</p>

CC BY-SA 3.0
2012-07-27T17:56:36.737Z
2012-07-27T17:56:36.737Z
Kristoffer Arnsfelt Hansen
<p>See also the recent paper of Daniel Kane and Ryan Williams, <a href="http://eccc.hpi-web.de/report/2015/188/">Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-2 and Depth-3 Threshold Circuits</a> (STOC 2016).</p>

<p>Ryan describes the paper as follows (the following description is taken from his homepage):</p>

<blockquote>
  <p>We give an explicit function in $\mathsf{PP}$ for which every majority of depth-two linear threshold circuits (with unbounded weights) needs about $n^{1.5}$ gates and $n^{2.5}$ wires, simultaneously. We also show that Andreev's function (computable by a depth-three majority circuit of $O(n)$ size) requires about the same gate and wire lower bound to be computed with depth-two linear threshold circuits. A key tool is the Littlewood-Offord Lemma, which we use to analyze the effect of random restrictions on the inputs of low-depth threshold circuits.</p>
</blockquote>

CC BY-SA 3.0
2016-05-02T22:03:54.893Z
2016-05-02T22:03:54.893Z
Yuval Filmus
<p>There are several well-known $\mathsf{AC^0}$ circuit size lower-bound results based on random restrictions and the <a href="http://en.wikipedia.org/wiki/Switching_lemma">Switching Lemma</a>.</p>

<p>Can we develop a Switching Lemma result to prove a size lower-bound for $\mathsf{TC^0}$ circuits (similar to the lower-bound proofs for $\mathsf{AC^0}$)? </p>

<p>Or is there any inherent obstacle to using this approach for proving $\mathsf{TC^0}$ lower-bounds? </p>

<p>Do barrier results like <a href="http://en.wikipedia.org/wiki/Natural_proof">Natural Proofs</a> say anything regarding using Switching Lemma like techniques to prove $\mathsf{TC^0}$ lower-bounds?</p>

CC BY-SA 3.0
2012-07-26T06:07:11.273Z
Are you familiar with the proof of switching lemma for $\mathsf{AC^0}$?
Kaveh
CC BY-SA 3.0
2012-07-26T07:01:44.437Z
I read the circuit lower bounds chapter of Arora's textbook.   Firstly, transform any constant depth cirtuit to a circuit without NOT gates with interleaving AND-OR layers, and secondly using the Switching Lemma switch this two layer, finaly we get a circuit top and the second level is the same AND (or OR) gates thus we can deprive the cicuit of one layer, redicing the circuit depth.
Jeigh
CC BY-SA 3.0
2012-07-26T07:16:15.073Z
However, it is not simplar than boolean case to observe the output of a gate when we fix several values of inputs(in the boolean case we fix about square root n inputs). AND gate and OR gate is extreme version of the threshhold gates and much easy to observe the influence of restrictions.
Jeigh
CC BY-SA 3.0
2012-07-26T16:13:28.403Z
The idea behind random restrictions technique is that an $\mathsf{AC^0}$ hit by a random restriction becomes simpler (in fact constant) with non-zero probability while keeping enough free variables. Unlike $\land$ and $\lor$ gates, a single $\mod p$ gate hit by a random restriction would still compute a $\mod p$ gate on smaller size inputs and will not become simpler.
Kaveh
CC BY-SA 3.0
2012-07-26T22:41:11.990Z
Note also that random restrictions and the Switching Lemma are one of prime examples of Natural Proofs. In any case, hopefully a circuit complexity expert will post a more comprehensive answer. ps: I took the liberty to rewrite the question, feel free to roll back if you don't like my edit.
Kaveh
<cc.complexity-theory><circuit-complexity><lower-bounds><boolean-functions>
Is it possible to use random restrictions to obtain a lower-bound for $\mathsf{TC^0}$?
Jeigh
# Is it possible to use random restrictions to obtain a lower-bound for $\mathsf{TC^0}$?

(Asked by: username_0 on 2012-07-26)

There are several well-known $\mathsf{AC^0}$ circuit size lower-bound results based on random restrictions and the [Switching Lemma](http://en.wikipedia.org/wiki/Switching_lemma).

Can we develop a Switching Lemma result to prove a size lower-bound for $\mathsf{TC^0}$ circuits (similar to the lower-bound proofs for $\mathsf{AC^0}$)?

Or is there any inherent obstacle to using this approach for proving $\mathsf{TC^0}$ lower-bounds?

Do barrier results like [Natural Proofs](http://en.wikipedia.org/wiki/Natural_proof) say anything regarding using Switching Lemma like techniques to prove $\mathsf{TC^0}$ lower-bounds?

**Tags:** cc.complexity-theory, circuit-complexity, lower-bounds, boolean-functions
> **Comments:**
> **username_1**: Are you familiar with the proof of switching lemma for $\mathsf{AC^0}$?  
> **username_0**: I read the circuit lower bounds chapter of Arora's textbook.   Firstly, transform any constant depth cirtuit to a circuit without NOT gates with interleaving AND-OR layers, and secondly using the Switching Lemma switch this two layer, finaly we get a circuit top and the second level is the same AND (or OR) gates thus we can deprive the cicuit of one layer, redicing the circuit depth.  
> **username_0**: However, it is not simplar than boolean case to observe the output of a gate when we fix several values of inputs(in the boolean case we fix about square root n inputs). AND gate and OR gate is extreme version of the threshhold gates and much easy to observe the influence of restrictions.  
> **username_1**: The idea behind random restrictions technique is that an $\mathsf{AC^0}$ hit by a random restriction becomes simpler (in fact constant) with non-zero probability while keeping enough free variables. Unlike $\land$ and $\lor$ gates, a single $\mod p$ gate hit by a random restriction would still compute a $\mod p$ gate on smaller size inputs and will not become simpler.  
> **username_1**: Note also that random restrictions and the Switching Lemma are one of prime examples of Natural Proofs. In any case, hopefully a circuit complexity expert will post a more comprehensive answer. ps: I took the liberty to rewrite the question, feel free to roll back if you don't like my edit.  

---

## 2 answers

### Answer by username_2 on 2012-07-27. Score: 12

It is actually possible to make use of random restrictions to prove lower bounds for threshold circuits.

In particular in the paper [Size-Depth Tradeoffs for Threshold Circuits](http://dx.doi.org/10.1137/S0097539792282965), Impagliazzo, Paturi, and Saks use random restrictions to prove a superliner lower bound (on the number of wires) for constant depth threshold circuits computing the parity function.

With regards to proving superpolynomial lower bounds for $\mathsf{TC}^0$
circuits then yes, the natural proof concept is of relevance since there are [constructions](http://dx.doi.org/10.1145/972639.972643) of pseudo-random function generators in $\mathsf{TC}^0$.


---

### Answer by username_3 on 2016-05-02. Score: 7

See also the recent paper of Daniel Kane and Ryan Williams, [Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-2 and Depth-3 Threshold Circuits](http://eccc.hpi-web.de/report/2015/188/) (STOC 2016).

Ryan describes the paper as follows (the following description is taken from his homepage):

> We give an explicit function in $\mathsf{PP}$ for which every majority of depth-two linear threshold circuits (with unbounded weights) needs about $n^{1.5}$ gates and $n^{2.5}$ wires, simultaneously. We also show that Andreev's function (computable by a depth-three majority circuit of $O(n)$ size) requires about the same gate and wire lower bound to be computed with depth-two linear threshold circuits. A key tool is the Littlewood-Offord Lemma, which we use to analyze the effect of random restrictions on the inputs of low-depth threshold circuits.


---

