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.