On the hardness of approximating the permanent of structured matrices

DOI10.1007/s00037-002-0174-3zbMath1048.15006OpenAlexW2045712190MaRDI QIDQ1430572

Bruno Codenotti, Arne Winterhof, Igor E. Shparlinski

Publication date: 27 May 2004

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-002-0174-3

zbMATH Keywords

exponential sumsfinite fieldsToeplitz matricessymmetric matricesWaring problemcirculant matricesHankel matricesstructured matriceshidden number problemapproximation of the permanent

Mathematics Subject Classification ID

Determinants, permanents, traces, other special matrix functions (15A15) Waring's problem and variants (11P05) Hermitian, skew-Hermitian, and related matrices (15B57) Exponential sums (11T23) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

A hidden number problem in small subgroups ⋮ Noisy interpolation of sparse polynomials in finite fields

This page was built for publication: On the hardness of approximating the permanent of structured matrices