Publications

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