Please use this identifier to cite or link to this item: https://doi.org/10.1007/s00037-002-0174-3
DC FieldValue
dc.titleOn the hardness of approximating the permanent of structured matrices
dc.contributor.authorCodenotti, B.
dc.contributor.authorShparlinski, I.E.
dc.contributor.authorWinterhof, A.
dc.date.accessioned2016-12-13T05:36:22Z
dc.date.available2016-12-13T05:36:22Z
dc.date.issued2002
dc.identifier.citationCodenotti, 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. https://doi.org/10.1007/s00037-002-0174-3
dc.identifier.issn10163328
dc.identifier.urihttp://scholarbank.nus.edu.sg/handle/10635/132773
dc.description.abstractWe 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.
dc.description.urihttp://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1007/s00037-002-0174-3
dc.sourceScopus
dc.subjectApproximation of the permanent
dc.subjectExponential sums
dc.subjectHidden number problem
dc.typeArticle
dc.contributor.departmentTEMASEK LABORATORIES
dc.description.doi10.1007/s00037-002-0174-3
dc.description.sourcetitleComputational Complexity
dc.description.volume11
dc.description.issue3-4
dc.description.page158-170
dc.identifier.isiut000186953300004
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

3
checked on Jan 23, 2023

WEB OF SCIENCETM
Citations

4
checked on Jan 23, 2023

Page view(s)

130
checked on Jan 26, 2023

Google ScholarTM

Check

Altmetric


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