Please use this identifier to cite or link to this item:
Title: On the hardness of approximating the permanent of structured matrices
Authors: Codenotti, B.
Shparlinski, I.E.
Winterhof, A. 
Keywords: Approximation of the permanent
Exponential sums
Hidden number problem
Issue Date: 2002
Citation: Codenotti, B., Shparlinski, I.E., Winterhof, A. (2002). On the hardness of approximating the permanent of structured matrices. Computational Complexity 11 (3-4) : 158-170. ScholarBank@NUS Repository.
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.
Source Title: Computational Complexity
ISSN: 10163328
DOI: 10.1007/s00037-002-0174-3
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.