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

We consider the ``minor'' and ``homeomorphic'' analogues of the maximum clique problem, i.e., the problems of determining the largest $h$ such that the input graph has a minor isomorphic to $K_h$ or a subgraph homeomorphic to $K_h,$ respectively.We show the former to be approximable within $O(\sqrt {n} \log^{1.5} n)$ by ... more >>>

Presented is an algorithm (for learning a subclass of erasing regular
pattern languages) which
can be made to run with arbitrarily high probability of
success on extended regular languages generated by patterns
$\pi$ of the form $x_0 \alpha_1 x_1 ... \alpha_m x_m$
for unknown $m$ but known $c$,
more >>>