Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with structured matrices:
TR02-071 | 6th June 2002
Bruno Codenotti, Igor E. Shparlinski

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

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

ISSN 1433-8092 | Imprint