Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with NP-hard problems:
TR97-046 | 3rd October 1997
Alexander Barg

Complexity Issues in Coding Theory

This is a research-expository paper. It deals with
complexity issues in the theory of linear block codes. The main
emphasis is on the theoretical performance limits of the
best known codes. Therefore, the main subject of the paper are
families of asymptotically good codes, i.e., codes whose rate and
relative ... more >>>

TR99-027 | 17th July 1999
Marek Karpinski, Igor E. Shparlinski

On the computational hardness of testing square-freeness of sparse polynomials

We show that deciding square-freeness of a sparse univariate
polynomial over the integer and over the algebraic closure of a
finite field is NP-hard. We also discuss some related open
problems about sparse polynomials.

more >>>

TR04-040 | 4th May 2004
Venkatesan Guruswami, Alexander Vardy

Maximum-likelihood decoding of Reed-Solomon codes is NP-hard

Maximum-likelihood decoding is one of the central algorithmic
problems in coding theory. It has been known for over 25 years
that maximum-likelihood decoding of general linear codes is
NP-hard. Nevertheless, it was so far unknown whether maximum-
likelihood decoding remains hard for any specific family of
more >>>

ISSN 1433-8092 | Imprint