On the hardness of approximating the permanent of structured matrices

Bruno Codenotti*, Igor E. Shparlinski, Arne Winterhof

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

Abstract

We show that for several natural classes of "structured" matrices, including symmetric, circulant, Hankel and Toeplitz matrices, approximating the permanent modulo a prime p is as hard as computing its exact value. Results of this kind are well known for arbitrary matrices. However the techniques used do not seem to apply to "structured" matrices. Our approach is based on recent advances in the hidden number problem introduced by Boneh and Venkatesan in 1996 combined with some bounds of exponential sums motivated by the Waring problem in finite fields.

Original languageEnglish
Pages (from-to)158-170
Number of pages13
JournalComputational Complexity
Volume11
Issue number3-4
DOIs
Publication statusPublished - 2002

Keywords

  • Approximation of the permanent
  • Exponential sums
  • Hidden number problem

Fingerprint Dive into the research topics of 'On the hardness of approximating the permanent of structured matrices'. Together they form a unique fingerprint.

Cite this