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

  • 5
    $\begingroup$ 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. $\endgroup$ – Alessandro Cosentino Oct 4 '13 at 15:08
  • 1
    $\begingroup$ 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. $\endgroup$ – domotorp Oct 4 '13 at 15:14
  • $\begingroup$ @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. $\endgroup$ – David Richerby Oct 4 '13 at 18:52
  • 1
    $\begingroup$ Are there any stronger theorems that imply Barrington's theorem? And do they use Barrington's theorem in the proof? $\endgroup$ – Peter Shor Oct 4 '13 at 19:38
  • 4
    $\begingroup$ @PeterShor: good point. Ben-Or and Cleve 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 :) $\endgroup$ – Alessandro Cosentino Oct 5 '13 at 1:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.