  List-decoding of Reed-Solomon (RS) codes beyond the so called Johnson radius
has been one of the main open questions since the work of Guruswami and Sudan.
It is now known by the work of Rudra and Wootters, using techniques from high
dimensional probability, that over large enough alphabets most RS codes are
indeed list-decodable beyond this radius.
  In this paper we take a more combinatorial approach which allows us to
determine the precise relation (up to the exact constant) between the decoding
radius and the list size. We prove a generalized Singleton bound for a given
list size, and conjecture that the bound is tight for most RS codes over large
enough finite fields. We also show that the conjecture holds true for list
sizes $2 \text{ and }3$, and as a by product show that most RS codes with a
rate of at least $1/9$ are list-decodable beyond the Johnson radius. Lastly, we
give the first explicit construction of such RS codes. The main tools used in
the proof are a new type of linear dependency between codewords of a code that
are contained in a small Hamming ball, and the notion of cycle space from Graph
Theory. Both of them have not been used before in the context of list-decoding.
