A Permanent Algorithm with exp[O (n ˆ{1/3}/2 ln n )] Expected Speedup for 0‐1 Matrices

This paper outlines a permanent algorithm with mildly exponential expected speedup over Ryser's inclusion and exclusion algorithm for 0‐1 matrices. The algorithm is based on a finite‐difference formula that is a generalization of Ryser's formula. The matrix is augmented by a column of entries selected to produce zero‐valued terms in the formula. The algorithm achieves speedup by avoiding computation of many zero‐valued terms.