On the hardness of approximating the permanent of structured matrices

Bruno Codenotti; Igor E. Shparlinski; Arne Winterhof

doi:10.1007/s00037-002-0174-3

On the hardness of approximating the permanent of structured matrices

Bruno Codenotti^*, Igor E. Shparlinski, Arne Winterhof

^*Corresponding author for this work

School of Computing

Research output: Contribution to journal › Article › peer-review

4 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 language	English
Pages (from-to)	158-170
Number of pages	13
Journal	Computational Complexity
Volume	11
Issue number	3-4
DOIs	https://doi.org/10.1007/s00037-002-0174-3
Publication status	Published - 2002

Keywords

Approximation of the permanent
Exponential sums
Hidden number problem

Access to Document

10.1007/s00037-002-0174-3

Cite this

@article{8950b1c5c96d4d8cb2b5e45f7e38a207,

title = "On the hardness of approximating the permanent of structured matrices",

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.",

keywords = "Approximation of the permanent, Exponential sums, Hidden number problem",

author = "Bruno Codenotti and Shparlinski, \{Igor E.\} and Arne Winterhof",

year = "2002",

doi = "10.1007/s00037-002-0174-3",

language = "English",

volume = "11",

pages = "158--170",

journal = "Computational Complexity",

issn = "1016-3328",

publisher = "Springer, Springer Nature",

number = "3-4",

}

TY - JOUR

T1 - On the hardness of approximating the permanent of structured matrices

AU - Codenotti, Bruno

AU - Shparlinski, Igor E.

AU - Winterhof, Arne

PY - 2002

Y1 - 2002

N2 - 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.

AB - 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.

KW - Approximation of the permanent

KW - Exponential sums

KW - Hidden number problem

UR - https://www.scopus.com/pages/publications/0346361846

U2 - 10.1007/s00037-002-0174-3

DO - 10.1007/s00037-002-0174-3

M3 - Article

AN - SCOPUS:0346361846

SN - 1016-3328

VL - 11

SP - 158

EP - 170

JO - Computational Complexity

JF - Computational Complexity

IS - 3-4

ER -

On the hardness of approximating the permanent of structured matrices

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this