# 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. Commented 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. Commented 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. Commented 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. Commented Dec 20, 2020 at 16:16