Define $SIZE$-$DEPTH(s, d)$ to be the functions which are computed by circuit families of size $O(s(n))$ and less than depth $d(n)$.

We know from Boppana's 1997 paper on the average sensitivity of low depth circuits that if we have functions $s, d, s', d' : \mathbb{N} \rightarrow \mathbb{N}$, where

$log(s(n))^{d(n)-1} = o(n)$,

$log(s'(n))^{d'(n) - 1} = o(log(s(n))^{d(n) - 1}$,

we know that $SIZE$-$DEPTH(s, d) \neq SIZE$-$DEPTH(s', d')$.

This is true because in $SIZE$-$DEPTH(s, d)$ we can compute $PARITY$ on a larger number of bits than in its $s', d'$ defined counterpart. This separates a large number of low complexity classes, most interesting to me being $qAC^0 \neq FOLL$. On the other hand, when

$log(s(n))^{d(n) - 1} = \Theta(log(s'(n))^{d'(n) - 1})$,

I don't know of a method to separate them. Obviously there are the degenerate cases where $s(n) = \Theta(s'(n)), d = \Theta(d')$, but I tried to compute the limit and get some constraints on $s, d, s', d'$ but it is seriously gnarly and it doesn't seem to give me anything good. If $d$ is constant you can do something but it doesn't give me much intuition. Can anybody come up with interesting examples, perhaps illustrating the size-depth tradeoffs that you'd imagine would be present, of $s, d, s', d'$ for which the respective classes cannot be separated by Boppana? If so, can you show a separation between these two classes in another way? Is there some reason I'm missing that all such cases are degenerate?


1 Answer 1


Lets say that we have $s, d$ where $log(s(n))^{d(n) - 1} = o(n)$. Let $d'(n)$ be arbitrary and $s'(n) = 2^{\sqrt[d'(n) - 1]{log(s(n))^{d(n) - 1}}}$. Then we have that $log(s(n))^{d(n) - 1} = log(s'(n))^{d'(n) - 1}$. Thus, we have a question, for various interesting ranges of $s, d, s'$, which is not seemingly answered by Boppana:

$SIZE$-$DEPTH(s, d) =_? SIZE$-$DEPTH(2^{\sqrt[d'(n) - 1]{log(s(n))^{d(n) - 1}}}, d'(n))$

Thinking about the limit was overcomplicating this clearly and this is easy to see. It shows the size-depth tradeoff I expected, as well, where the new size goes up as the depth goes down, making the circuit "harder to beat" in both directions. I think, speaking of this, that you will be able to show that these classes are incomparable. Does anybody else have any thoughts on the relationship between the two classes and can you prove something about it?


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.