Computing sparse permanents faster

Bax and Franklin (2002) gave a randomized algorithm for exactly computing the permanent of any n×n zero-one matrix in expected time exp[−Ω(n1/3/(2lnn))]2n. Building on their work, we show that for any constant C>0 there is a constant ɛ>0 such that the permanent of any n×n (real or complex) matrix with at most Cn nonzero entries can be computed in deterministic time (2−ɛ)n and space O(n). This improves on the Ω(2n) runtime of Ryser's algorithm for computing the permanent of an arbitrary real or complex matrix.