List decoding of the first-order Reed-Muller codes RM(1,m) is considered within the
radius $n(1-\epsilon)/2$ for any length $n = 2^m$ and an arbitrarily small 
$\epsilon > 0$. 
The well Green algorithm of maximum likelihood decoding performs the order 
of $O(n \ln^2 n)
bit operations to find the closest codeword of RM(1,m), whereas the 
Litsyn-Shekhovtsov
algorithm has linear complexity O(n) and executes bounded-distance decoding 
within the
radius $n/4-1$. We close the performance gap between the two algorithms as 
follows. First, for
any biorthogonal code RM(1,m), we design an algorithm, which outputs the 
complete list of
codewords within a decoding radius $n(1-\epsilon)/2$ and has complexity order of 
$n\ln^2 \min\{\epsilon^{-2},n\}$.
Here we also show that the output list of codewords has maximum size of order 
$\min\{\epsilon^{-2},n\}$.
For any small constant, this decoding has linear complexity and almost twice 
the radius
of bounded distance decoding. The new algorithm also reduces complexity 
$O(n \ln^2 n)$ of ML
decoding, if $\epsilon$ decays slower than $n^{-1/2}$. Otherwise, the algorithm 
produces the output lists
of size $O(n)$ and has full complexity $O(n \ln^2 n)$ of ML decoding.
Second, we generalize our algorithm for non-Hamming (for example, 
the Euclidean) metrics. Finally, we address the randomized versions of our algorithms that 
allow incorrect
(incomplete or excessive) lists with a small error probability P. This setting 
was first considered
ered by O. Goldreich and L. Levin who designed in 1989 a randomized algorithm 
that has
poly-logarithmic complexity $poly( \frac{m}{\epsilon}\ln \frac{1}{})$. Our new 
algorithm also achieves 
poly-logarithmic and yields a lower complexity order in parameter $\epsilon$.