Permanents of Circulants: a Transfer Matrix Approach (Expanded Version)

Mordecai J. Golin, Yiu Cho Leung, Yajun Wang

Calculating the permanent of a (0,1) matrix is a #P-complete problem but there are some classes of structured matrices for which the permanent is calculable in polynomial time. The…