For every $0 < R < 1$ and $\eps > 0$, we present an explicit
construction of error-correcting codes of rate $R$ that can be list
decoded in polynomial time up to a fraction $(1-R-\eps)$ of errors.
These codes achieve the ``capacity'' for decoding from {\em ... more >>>

This paper is concerned with a new family of error-correcting codes
based on algebraic curves over finite fields, and list decoding
algorithms for them. The basic goal in the subject of list decoding is
to construct error-correcting codes $C$ over some alphabet $\Sigma$
which have good rate $R$, and at ... more >>>

We consider the following simple algorithm for feedback arc set problem in weighted tournaments --- order the vertices by their weighted indegrees. We show that this algorithm has an approximation guarantee of $5$ if the weights satisfy \textit{probability constraints}
(for any pair of vertices $u$ and $v$, $w_{uv}+w_{vu}=1$). Special cases ... more >>>