A Note on Barrington's Theorem
Authors: D. Boneh
Abstract:
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.
Reference:
web note
Full paper: html