A Note on Barrington's TheoremAuthors: D. Boneh
In several applications of Barrington's theorem to cryptography it is more convenient to use a group of 2x2 matrices instead of the symmetric group S5. The final branching program is a product of 2x2 matrices rather than a product of permutations. In this short note we list a few example 2x2 matrices that make Barrington's theorem work as efficiently as in S5. We also show how to implement an XOR gate efficiently in matrix branching programs.
Full paper: html