On the hardness of approximating the permanent of structured matrices (Articolo in rivista)

Type

• Articolo in rivista (Classe)
• Prodotto della ricerca (Classe)

Label

• On the hardness of approximating the permanent of structured matrices (Articolo in rivista) (literal)

Anno

• 2003-01-01T00:00:00+01:00 (literal)

Alternative label

• Codenotti B.,Shparlinski I., Winterhof A. (2003)
  On the hardness of approximating the permanent of structured matrices
  in Computational complexity
  (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori

• Codenotti B.,Shparlinski I., Winterhof A. (literal)

Pagina inizio

• 158 (literal)

Pagina fine

• 170 (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume

• 11 (literal)

Rivista

• Computational complexity (Rivista)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#note

• pubblicato nel 2003 (literal)

Note

• ISI Web of Science (WOS) (literal)

Titolo

• On the hardness of approximating the permanent of structured matrices (literal)

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. (literal)

Prodotto di

• Institute for informatics and telematics (IIT) (Istituto)

Autore CNR

• BRUNO CODENOTTI (Persona)

Incoming links:

Prodotto

• Institute for informatics and telematics (IIT) (Istituto)

Autore CNR di

• BRUNO CODENOTTI (Persona)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi

• Computational complexity (Rivista)