  The paper introduces the simultaneous partial-inverse problem (SPI) for
polynomials and develops its application to decoding interleaved Reed--Solomon
codes beyond half the minimum distance. While closely related both to standard
key equations and to well-known Pad\'e approximation problems, the SPI problem
stands out in several respects. First, the SPI problem has a unique solution
(up to a scale factor), which satisfies a natural degree bound. Second, the SPI
problem can be transformed (monomialized) into an equivalent SPI problem where
all moduli are monomials. Third, the SPI problem can be solved by an efficient
algorithm of the Berlekamp--Massey type. Fourth, decoding interleaved
Reed--Solomon codes (or subfield-evaluation codes) beyond half the minimum
distance can be analyzed in terms of a partial-inverse condition for the error
pattern: if that condition is satisfied, then the (true) error locator
polynomial is the unique solution of a standard key equation and can be
computed in many different ways, including the well-known multi-sequence
Berlekamp--Massey algorithm and the SPI algorithm of this paper. Two of the
best performance bounds from the literature (the Schmidt--Sidorenko--Bossert
bound and the Roth--Vontobel bound) are generalized to hold for the
partial-inverse condition and thus to apply to several different decoding
algorithms.
