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 - http://www.scopus.com/inward/record.url?scp=0346361846&partnerID=8YFLogxK
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 -