Computing Permanents on a Trellis
share
The problem of computing the permanent of a matrix has attracted interest since the work of Ryser(1963) and Valiant(1979). On the other hand, trellises were extensively studied in coding theory since the 1960s. In this work, we establish a connection between the two domains. We introduce the canonical trellis T_n that represents all permutations, and show that the permanent of a n by n matrix A can be computed as a flow on this trellis. Under certain normalization, the trellis-based method invokes slightly less operations than best known exact methods. Moreover, if A has structure, then T_n becomes amenable to vertex merging, thereby significantly reducing its complexity. - Repeated rows: Suppose A has only t<n distinct rows. The best known method to compute per(A), due to Clifford and Clifford (2020), has complexity O(n^t+1). Merging vertices in T_n, we obtain a reduced trellis that has complexity O(n^t). - Order statistics: Using trellises, we compute the joint distribution of t order statistics of n independent, but not identically distributed, random variables in time O(n^t+1). Previously, polynomial-time methods were known only when the variables are drawn from two non-identical distributions. - Sparse matrices: Suppose each entry in A is nonzero with probability d/n with d is constant. We show that T_n can be pruned to exponentially fewer vertices, resulting in complexity O(ϕ^n) with ϕ<2. - TSP: Intersecting T_n with another trellis that represents walks, we obtain a trellis that represents circular permutations. Using the latter trellis to solve the traveling salesperson problem recovers the well-known Held-Karp algorithm. Notably, in all cases, the reduced trellis are obtained using known techniques in trellis theory. We expect other trellis-theoretic results to apply to other structured matrices.
READ FULL TEXT