The subexponential tag has no wiki summary.
20
votes
1answer
381 views
Does $\mathsf{P/poly}$ have subexponential-size bounded-depth circuits?
Is there any plausible complexity/crypto hypothesis that rules out the possibility that polynomial size circuits have subexponential-size (i.e. $2^{O(n^\epsilon)}$ with $\epsilon<1$) bounded-depth ...
