<p>After reading the comments to get clearer on the motivation, I think we can say two things (one from the comments, one perhaps not mentioned yet):</p>
<ol>
<li><p>Given the lack of responses, even with attention from many people on this site including many experts, it seems likely that no such alternative proof is currently known.</p>
</li>
<li><p>&quot;Algebra is necessary (given our curren state of complexity understanding)&quot;. To clarify/extend some of the comments of Peter Shor and Sasho Nikolov: it's not just that <em>Barrington's particular construction</em> uses non-solvability of the group (which is true), it is that, assuming <span class="math-container">$\mathsf{NC}^1 \neq \mathsf{ACC}^0$</span>, G-permutation branching programs are <span class="math-container">$\mathsf{NC}^1$</span>-complete <em>if and only if</em> G is non-solvable. In <a href="https://doi.org/10.1016/0022-0000(89)90037-8" rel="noreferrer">Barrington's original paper</a> he showed (Theorem 6) that if G is solvable, then G-PBPs can only compute languages in <span class="math-container">$\mathsf{ACC}^0$</span>.</p>
</li>
</ol>
<p>So, a &quot;truly different proof&quot; seems like it would have to do at least one of two things: either show that <span class="math-container">$\mathsf{NC}^1 = \mathsf{ACC}^0$</span>, or give a different characterization of non-solvable groups. Now, there are of course many characterizations of solvable groups, so the second possibility seems somewhat plausible (whereas the first seems unlikely to me, though of course we don't even understand the power of MOD<span class="math-container">$_6$</span> gates, so who knows how powerful <span class="math-container">$\mathsf{ACC}^0$</span> might be...).</p>
<p>And in fact, the <span class="math-container">$\mathsf{NC}^1=\mathsf{ACC}^0$</span> alternative above is even more restrictive than as phrased above. I believe it follows from the proof technique of Barrington's Theorem 6 that if <span class="math-container">$G$</span> is a group with <span class="math-container">$\ell$</span> composition factors, then <span class="math-container">$G$</span>-PBPs can be simulated by circuits of depth <span class="math-container">$\ell$</span>, where all the gates at layer <span class="math-container">$i$</span> are MOD<span class="math-container">$_{p_i}$</span> gates, where <span class="math-container">$p_i$</span> is the order of the <span class="math-container">$i$</span>-th composition factor of <span class="math-container">$G$</span>. So if one could show that there is some solvable <span class="math-container">$G$</span> such that <span class="math-container">$G$</span>-PBPs capture <span class="math-container">$\mathsf{NC}^1$</span>, it would put <span class="math-container">$\mathsf{NC}^1$</span> into this (seemingly) more restricted subclass of <span class="math-container">$\mathsf{ACC}^0$</span>.</p>
<p><a href="https://doi.org/10.1016/0890-5401(90)90007-5" rel="noreferrer">Barrington, Straubing, and Therien</a> then showed that G-PBPs where G is nilpotent cannot even compute the AND function (that is, for any nilpotent group G, there is a sufficiently large <span class="math-container">$n$</span> such that the AND of <span class="math-container">$n$</span> bits cannot be computed by <em>any</em> G-PBP, regardless of length). They also showed that when <span class="math-container">$G$</span> is solvable, <span class="math-container">$G$</span>-PBPs can compute the AND function (the upper bound is exponential).</p>

CC BY-SA 4.0
2024-07-05T18:52:38.047Z
2024-07-05T18:52:38.047Z
Joshua Grochow
<p>I know that you can use other non-solvable groups, but is there a proof that uses a completely different approach?</p>

<p>In case someone would not know the theorem:
<a href="http://en.wikipedia.org/wiki/NC_(complexity)#Barrington.27s_theorem">http://en.wikipedia.org/wiki/NC_(complexity)#Barrington.27s_theorem</a></p>

CC BY-SA 3.0
2013-10-04T15:08:41.660Z
The original proof is so beautiful and _simple_, why seeking an alternative proof? :) More seriously, I wonder if there is any particular motivation behind the question.
Alessandro Cosentino
CC BY-SA 3.0
2013-10-04T15:14:34.600Z
My original motivation is simply that I wanted to tell in class that "no other proof is known"... But besides, I am also interested to know if there is another method, as it might be another good trick to learn.
domotorp
CC BY-SA 3.0
2013-10-04T18:52:02.037Z
@domotorp What weight does "no other proof is known" carry? There could be no other proof either because it's difficult to find one or because nobody has felt the need to find one.
David Richerby
CC BY-SA 3.0
2013-10-04T19:35:38.513Z
@David: At least it shows that it is not trivial to get rid of group theory. But you are right, maybe no one felt the need to find another...
domotorp
CC BY-SA 3.0
2013-10-04T19:38:37.230Z
Are there any stronger theorems that imply Barrington's theorem? And do they use Barrington's theorem in the proof?
Peter Shor 
CC BY-SA 3.0
2013-10-04T20:23:53.970Z
@domotorp But it *doesn't* show that it's not trivial to get rid of the group theory: maybe it's just that nobody has felt sufficiently motivated to try.
David Richerby
CC BY-SA 3.0
2013-10-05T01:02:59.810Z
@PeterShor: good point. [Ben-Or and Cleve](http://dx.doi.org/10.1137/0221006) did prove a generalization of Barrington's theorem for algebraic formulas over arbitrary rings. They don't black-box Barrington's theorem, but I wouldn't say that their proof "uses a completely different approach", as the OP requested. AFAIU the magic there happens because of the group SL(3,R) instead of S_5, but it's the same kind of magic :)
Alessandro Cosentino
CC BY-SA 3.0
2013-10-06T05:08:39.907Z
While the proof is amazing, it does feel like magic. It's worth seeing if that magic is somehow necessary. Is there any reason why the algebra is necessary for this result?
Sasho Nikolov
CC BY-SA 3.0
2013-11-10T10:49:17.697Z
@Sasho: if I remember correctly, Barrington's theorem applies to a group if and only if the group is non-solvable. Doesn't this show that some algebra is necessary?
Peter Shor 
CC BY-SA 3.0
2013-11-10T23:33:03.593Z
@Peter correct me if I am misunderstanding you: I am thinking of the theorem "polysize formulas have polynomial size constant width branching programs (BPs)". Are you saying that the Barrington's construction works only if a non-solvable group is used (I agree but I am not sure this implies that the algebra is intrinsic to the theorem) or are you saying that there is some sense in which the kind of restricted BPs Barrington considers capture the power of arbitrary bounded-width BPs?
Sasho Nikolov
CC BY-SA 3.0
2013-11-10T23:59:20.180Z
@Sasho: I'm saying your first alternative: Barrington's construction relies on non-solvable groups, so it seems like it's intrinsically algebraic. My comment gives my intuition about this, but it certainly isn't rigorous.
Peter Shor 
<circuit-complexity><gr.group-theory><formulas>
Are there other proofs for Barrington's theorem?
domotorp
# Are there other proofs for Barrington's theorem?

(Asked by: username_0 on 2013-10-04)

I know that you can use other non-solvable groups, but is there a proof that uses a completely different approach?

In case someone would not know the theorem:
<http://en.wikipedia.org/wiki/NC_(complexity)#Barrington.27s_theorem>

**Tags:** circuit-complexity, gr.group-theory, formulas
> **Comments:**
> **username_1**: The original proof is so beautiful and _simple_, why seeking an alternative proof? :) More seriously, I wonder if there is any particular motivation behind the question.  
> **username_0**: My original motivation is simply that I wanted to tell in class that "no other proof is known"... But besides, I am also interested to know if there is another method, as it might be another good trick to learn.  
> **username_2**: @domotorp What weight does "no other proof is known" carry? There could be no other proof either because it's difficult to find one or because nobody has felt the need to find one.  
> **username_0**: @David: At least it shows that it is not trivial to get rid of group theory. But you are right, maybe no one felt the need to find another...  
> **username_3**: Are there any stronger theorems that imply Barrington's theorem? And do they use Barrington's theorem in the proof?  
> **username_2**: @domotorp But it *doesn't* show that it's not trivial to get rid of the group theory: maybe it's just that nobody has felt sufficiently motivated to try.  
> **username_1**: @PeterShor: good point. [Ben-Or and Cleve](http://dx.doi.org/10.1137/0221006) did prove a generalization of Barrington's theorem for algebraic formulas over arbitrary rings. They don't black-box Barrington's theorem, but I wouldn't say that their proof "uses a completely different approach", as the OP requested. AFAIU the magic there happens because of the group SL(3,R) instead of S_5, but it's the same kind of magic :)  
> **username_4**: While the proof is amazing, it does feel like magic. It's worth seeing if that magic is somehow necessary. Is there any reason why the algebra is necessary for this result?  
> **username_3**: @Sasho: if I remember correctly, Barrington's theorem applies to a group if and only if the group is non-solvable. Doesn't this show that some algebra is necessary?  
> **username_4**: @Peter correct me if I am misunderstanding you: I am thinking of the theorem "polysize formulas have polynomial size constant width branching programs (BPs)". Are you saying that the Barrington's construction works only if a non-solvable group is used (I agree but I am not sure this implies that the algebra is intrinsic to the theorem) or are you saying that there is some sense in which the kind of restricted BPs Barrington considers capture the power of arbitrary bounded-width BPs?  
> **username_3**: @Sasho: I'm saying your first alternative: Barrington's construction relies on non-solvable groups, so it seems like it's intrinsically algebraic. My comment gives my intuition about this, but it certainly isn't rigorous.  

---

## 1 answers

### Answer by username_5 on 2024-07-05. Score: 9 | Accepted answer

After reading the comments to get clearer on the motivation, I think we can say two things (one from the comments, one perhaps not mentioned yet):

1. Given the lack of responses, even with attention from many people on this site including many experts, it seems likely that no such alternative proof is currently known.
2. "Algebra is necessary (given our curren state of complexity understanding)". To clarify/extend some of the comments of Peter Shor and Sasho Nikolov: it's not just that *Barrington's particular construction* uses non-solvability of the group (which is true), it is that, assuming $\mathsf{NC}^1 \neq \mathsf{ACC}^0$, G-permutation branching programs are $\mathsf{NC}^1$-complete *if and only if* G is non-solvable. In [Barrington's original paper](https://doi.org/10.1016/0022-0000(89)90037-8) he showed (Theorem 6) that if G is solvable, then G-PBPs can only compute languages in $\mathsf{ACC}^0$.

So, a "truly different proof" seems like it would have to do at least one of two things: either show that $\mathsf{NC}^1 = \mathsf{ACC}^0$, or give a different characterization of non-solvable groups. Now, there are of course many characterizations of solvable groups, so the second possibility seems somewhat plausible (whereas the first seems unlikely to me, though of course we don't even understand the power of MOD$\_6$ gates, so who knows how powerful $\mathsf{ACC}^0$ might be...).

And in fact, the $\mathsf{NC}^1=\mathsf{ACC}^0$ alternative above is even more restrictive than as phrased above. I believe it follows from the proof technique of Barrington's Theorem 6 that if $G$ is a group with $\ell$ composition factors, then $G$-PBPs can be simulated by circuits of depth $\ell$, where all the gates at layer $i$ are MOD$\_{p\_i}$ gates, where $p\_i$ is the order of the $i$-th composition factor of $G$. So if one could show that there is some solvable $G$ such that $G$-PBPs capture $\mathsf{NC}^1$, it would put $\mathsf{NC}^1$ into this (seemingly) more restricted subclass of $\mathsf{ACC}^0$.

[Barrington, Straubing, and Therien](https://doi.org/10.1016/0890-5401(90)90007-5) then showed that G-PBPs where G is nilpotent cannot even compute the AND function (that is, for any nilpotent group G, there is a sufficiently large $n$ such that the AND of $n$ bits cannot be computed by *any* G-PBP, regardless of length). They also showed that when $G$ is solvable, $G$-PBPs can compute the AND function (the upper bound is exponential).


---

