Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR02-071 | 6th June 2002 00:00

Non-approximability of the Permanent of Structured Matrices over Finite Fields

RSS-Feed




TR02-071
Authors: Bruno Codenotti, Igor E. Shparlinski
Publication: 16th December 2002 04:08
Downloads: 950
Keywords: 


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 the exact value. Results of this kind are well known for the class of 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.



ISSN 1433-8092 | Imprint