International Association for Cryptologic Research
The interplay between group theory and computational complexity has been the source of a number of elegant constructions and computational insights. A line of work [Bar89, CM87, BT88, BC92, CL94, Cle91, and IL95] in the late 1980s gave characterizations of various complexity classes in terms of products over finite groups. A primary motivation of some of this paper was to obtain an efficient simulation of circuits by branching programs, such as in the celebrated theorem of Barrington [Bar89]. Beyond this however, the underlying encoding of computation by group products has proven to be a useful tool in other areas.