What circuit depth is enough to compute a log-space complete problem?

To the best of my knowledge it is unknown that $$\mathsf{L}$$ is subset of $$\mathsf{NC}^1$$.

(Here $$\mathsf{NC}^1$$ is the class of decision problems solvable by a family of Boolean circuits, with polynomial size, logarithmic depth , and bounded fan-in;

$$\mathsf{L}$$ is the class of decision problems solvable by a Turing machine restricted to use an amount of memory logarithmic in the size of the input.)

Let reduce restriction in the definition of $$\mathsf{NC}^1$$: assume we allow size, say $$n^{O(\log \log n)}$$ and depth $$O(\log n \log \log n)$$. Can we solve any problem in $$\mathsf{L}$$ by such circuits?

Are there any natural conjectures about it?

• $L\subseteq NC^2$ is known and so $n^{O(1)}$ size and depth $O(\log^2n)$ suffices. The OP is asking for tradeoffs between size and depth. Commented Feb 8, 2023 at 18:41
• $NC^2 \subseteq quasiNC^1$ (log-depth, quasi-poly size), and I think this is the best known size upper bound on log-depth circuits to compute $NC^2$ problems. If you ask about size upper bound on log-depth circuits to compute logspace, I don't know if anything better is known (but I kinda doubt it...). Commented Feb 8, 2023 at 19:03
• @JoshuaGrochow Could you please give a reference about quasi$NC^{1}$? Your definition confuses me: if depth is $O(\log n)$ and fan-in is bounded then output depends on poly(n) vertices, isn't it? Commented Feb 8, 2023 at 19:35
• @AlexeyMilovanov: Yes, but...vertices of what? There are only n input bits. I'll see if I can dig up a ref about quasiNC^1 Commented Feb 8, 2023 at 19:42
• By the way, in the question, depth $O(\log n\log\log n)$ by itself implies size $n^{O(\log\log n)}$, making the $n^{O(\log n)}$ bound redundant. Commented Feb 9, 2023 at 7:28

I'm quite sure that no better depth upper bound is known for L than $$\log^2 n$$, in the bounded fan-in circuit model, even with no size restriction.
In the semi-unbounded fan-in circuit model (fan-in 2 AND and unbounded fan-in OR), log-depth is adequate to recognize not only L, but also NL, with polynomial size. This class, known as $$SAC^1$$ is equal to the class of problems logspace-reducible to a context-free language, and it has several equivalent characterizations.
The "natural conjecture" would be that $$\log^2 n$$ is optimal ... but there's not much evidence to support that conjecture.