Is it possible to use random restrictions to obtain a lower-bound for $\mathsf{TC^0}$?

There are several well-known $\mathsf{AC^0}$ circuit size lower-bound results based on random restrictions and the 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 say anything regarding using Switching Lemma like techniques to prove $\mathsf{TC^0}$ lower-bounds?

• Are you familiar with the proof of switching lemma for $\mathsf{AC^0}$? Commented Jul 26, 2012 at 6:07
• 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. Commented Jul 26, 2012 at 7:01
• 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. Commented Jul 26, 2012 at 7:16
• 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. Commented Jul 26, 2012 at 16:13
• 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. Commented Jul 26, 2012 at 22:41

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 of pseudo-random function generators in $\mathsf{TC}^0$.
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.