Approximating permanents of complex matrices

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations


A wide variety of approximation algorithms for permanents of non-negative matrices has been proposed and analyzed before [5; 7; 9; 1]. Usually, these approximation algorithms have been presented for 0-1 matrices and it has been remarked that they extend to other matrices as long as all entries are non-negative. Here we present the first approximation algorithm for the permanent of an arbitrary complex matrix. We extend the notion of an (ε,δ)-approximation algorithm to accommodate for cancellations in additions. Our running time is Õ(3n/2 ε-2 log 1/δ) compared to Õ(2n/2 ε-2 log 1/δ) for non-negative matrices. (A faster algorithm is known for 0-1 matrices [6].).

Original languageEnglish (US)
Title of host publicationProceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC 2000
Number of pages3
StatePublished - 2000
Event32nd Annual ACM Symposium on Theory of Computing, STOC 2000 - Portland, OR, United States
Duration: May 21 2000May 23 2000

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017


Conference32nd Annual ACM Symposium on Theory of Computing, STOC 2000
Country/TerritoryUnited States
CityPortland, OR

All Science Journal Classification (ASJC) codes

  • Software


Dive into the research topics of 'Approximating permanents of complex matrices'. Together they form a unique fingerprint.

Cite this