# 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