13
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ Are you familiar with the proof of switching lemma for $\mathsf{AC^0}$? $\endgroup$ – Kaveh Jul 26 '12 at 6:07
  • 1
    $\begingroup$ 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. $\endgroup$ – Jeigh Jul 26 '12 at 7:01
  • 1
    $\begingroup$ 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. $\endgroup$ – Jeigh Jul 26 '12 at 7:16
  • 2
    $\begingroup$ 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. $\endgroup$ – Kaveh Jul 26 '12 at 16:13
  • $\begingroup$ 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. $\endgroup$ – Kaveh Jul 26 '12 at 22:41
11
$\begingroup$

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

Improve this answer
$\endgroup$
6
$\begingroup$

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 (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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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