Multiplicity Codes: Locality with High Efficiency
Madhu Sudan (MSR New England)
The increasing imbalance between size of data and computational power
available to users has led to the notion of ``sublinear time algorithms",
namely algorithms that run in time less than the size of the data they
are processing. This notion seems to be especially relevant in the
context of error-detection/correction where the notion suggests that
one could get the reliability benefits offered by packaging data in
large blocks, while not losing (proportionately) in the time delay
of error-detection/decoding. Codes that allow for such effects are
known as locally testable codes and locally decodable codes.
Research over the past two decades has resulted in some very interesting
constructions and applications of locally decodable codes. However,
somewhat strikingly, while in theory these codes should be of great
practical interest, in practice they have been used only in theory
(of complexity and cryptography)! We argue that the reason for this
is that till recently these codes had very poor rate (ratio of message
length to redundancy). A recent development (Kopparty, Saraf, and
Yekhanin, STOC 2011) overcomes this barrier leading to codes of
arbitrarily high rate for the the first time. In this talk we will
describe the context and their, very elegant, construction which makes
the powerful use of derivatives of polynomials.