Clifford algebras and approximating the permanent

DOI10.1016/S0022-0000(03)00010-2zbMath1066.68160MaRDI QIDQ5917579

Steve Chien, Alistair Sinclair, Lars Rasmussen

Publication date: 18 November 2004

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

permanentsquaternionsexplicit algorithmsecond Clifford algebra

Mathematics Subject Classification ID

Determinants, permanents, traces, other special matrix functions (15A15) Randomized algorithms (68W20)

Related Items

Concentration of permanent estimators for certain large matrices., Random path method with pivoting for computing permanents of matrices, Unnamed Item, On the hardness of the noncommutative determinant, Unnamed Item, Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees, A load balancing strategy for parallel computation of sparse permanents, Noncommutativity makes determinants hard

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• A theory of noncommutative determinants and characteristic functions of graphs
• Quaternionic determinants
• Approximating the number of monomer-dimer coverings of a lattice.
• An analysis of Monte Carlo algorithm for estimating the permanent
• A mildly exponential approximation algorithm for the permanent
• Approximating the Permanent
• A Monte-Carlo Algorithm for Estimating the Permanent
• Approximating the permanent: A simple approach
• Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor
• A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries
• A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents