# 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}$? Jul 26 '12 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. Jul 26 '12 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. Jul 26 '12 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. Jul 26 '12 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. Jul 26 '12 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.