For Reed-Solomon codes with block length n and dimension k, the Johnson theorem states that for a Hamming ball of radius smaller than n - sqrt(n k), there can be at most O (n2) codewords. It was not known whether for larger radius, the number of codewords is polynomial. The best known list decoding algorithm for Reed-Solomon codes due to Guruswami and Sudan [Venkatesan Guruswami, Madhu Sudan, Improved decoding of Reed-Solomon and algebraic-geometry codes, IEEE Transactions on Information Theory 45 (6) (1999) 1757-1767] is also known to work in polynomial time only within this radius. In this paper we prove that when k < α n for any constant 0 < α < 1, we can overcome the barrier of the Johnson bound for list decoding of Reed-Solomon codes (even if the field size is exponential). More specifically in such a case, we prove that for Hamming ball of radius n - sqrt(n k) + c (for any c > 0) there can be at most O (nc frac(2 sqrt(α), (1 - sqrt(α))2) + c + 2) number of codewords. For any constant c, we describe a polynomial time algorithm for enumerating all of them, thereby also improving on the Guruswami-Sudan algorithm. Although the improvement is modest, this provides evidence for the first time that the n - sqrt(n k) bound is not sacrosanct for such a high rate. We apply our method to obtain sharper bounds on a list recovery problem introduced by Guruswami and Rudra [Venkatesan Guruswami, Atri Rudra, Limits to list decoding Reed-Solomon codes, IEEE Transactions on Information Theory 52 (8) (2006) 3642-3649] where they establish super-polynomial lower bounds on the output size when the list size exceeds ⌈ frac(n, k) ⌉. We show that even for larger list sizes the problem can be solved in polynomial time for certain values of k. © 2008 Elsevier B.V. All rights reserved.