# Closure properties of Alternating Circuit 1 level

Recall that $$\mathsf{AC^1}$$ is the class of circuits with unbounded fan-in, polynomial size, and logarithmic depth.

Is this class closed under Kleene star? I thought it would be simple since it is easy to check every subword (using a polynomial number of gates), but the part where I have to check every partition makes the circuit linear in depth.

Denote your language by $$L$$. Let the input be $$x_1,\ldots,x_n$$. Let $$f(i,j,\ell)$$ be true if $$x_1,\ldots,x_j \in L^\ell$$. The output will be $$\bigvee_{\ell=1}^n f(1,n,\ell).$$ When $$\ell = 1$$, there is an $$\mathsf{AC^1}$$ circuits for $$f(i,j,\ell)$$. When $$\ell > 1$$, we use the formula $$f(i,j,\ell) = \bigvee_{k=i}^{j-1} (f(i,k,\lfloor \ell/2 \rfloor) \land f(k+1,j,\lceil\ell/2\rceil)).$$ The resulting circuit is still $$\mathsf{AC^1}$$, since there are only $$O(\log n)$$ levels of recursion.
A different way of looking at this construction is to notice that for inputs of length $$L$$, we can replace $$L^*$$ with $$L \cup \cdots \cup L^n$$; and that $$L^m$$ can be computed in $$O(\log m)$$ steps using repeated squaring.
• I posit this circuit is not in $AC^1$, since it is not of polynomial size. Let $s(i, j, l)$ be the size of the circuit for $f(i, j, l)$. We can generously assume $s(i, j, 1) \geq 1$. Thus $s(1, n, l) = \sum_{k = 1}^{n - 1} s(1, k, l / 2) + s(k + 1, n, l / 2)$ for which the best limit I can think of is $\mathcal{O}(n s(1, n, l / 2))$. And the recurrence relation $g(n) = ng(n/2), g(1) = 1$ solves to $\mathcal{O}(n^{\log n})$, which is quasipolynomial. I might be wrong, but either way, I'd say that you need to prove that the result has polynomial size, as it is not immediately obvious. Dec 20, 2020 at 16:03
• You can compute each $f(i,j,\ell)$ from other values of $f$ using $O(n)$ gates. Since there are $O(n^3)$ many choices for $i,j,\ell$, the resulting circuit has $O(n^4)$ gates. Dec 20, 2020 at 16:12
• Your recurrence might make sense if we were constructing a formula. Fortunately, we are constructing a circuit, so we only have to compute each $f(i,j,\ell)$ once. This is akin to dynamic programming. Dec 20, 2020 at 16:13
• Right, so my naive way would take some subproblem circuits more than once, but if we deduplicate that we get a straightforward limit of $\mathcal{O}(n^3)$. That does make sense, thanks. Dec 20, 2020 at 16:16