2021/07/15 by Han Mao Kiah, Kiah, Han Mao, Alexander Vardy +3
Computer Science · Mathematics · #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Markov Chains and Monte Carlo Methods #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2107.07377
openalex publication_date 2021/07/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Tn 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 Tn becomes amenable to vertex merging, thereby significantly reducing its complexity. - Repeated rows: Suppose A has only t