The 60+ years of research in coding theory gave us nearly optimal ways to add redundancy to messages, encoding bit strings representing messages into longer bit strings called codewords, in a way that the message can still be recovered even if a certain fraction of the codeword bits are corrupted. The decoding time of classical error-correcting however typically increases at least linearly with the length of the message. Thus recovering even a single message bit requires a substantial amount of computation. Locally decodable codes are codes intended to address this seeming conflict between efficient retrievability and reliability. The simplest locally decodable code is the Hadamard code encoding $ 3 $-bit messages $ (x_1, x_2, x_3) $ to $ \mbox{7} $-bit codewords $ (x_1,x_2,x_3,x_1\oplus x_2, x_1\oplus x_3, x_2\oplus x_3, x_1\oplus x_2\oplus x_3) $. It is not hard to verify that even after some arbitrary three codeword coordinates are erased, one can still recover any particular missing message symbol by reading only two (out of four) remaining codeword symbols. For instance, if symbols $ x_1,x_2, x_1\oplus x_3 $ are missing one can recover $ x_1 $ by reading $ x_2\oplus x_3 $ and $ x_1\oplus x_2\oplus x_3. $
The theory of locally decodable codes is relatively young and actively developing. Locally decodable codes have applications in computational complexity theory and cryptography. They are also used in practice to ensure reliability in large distributed data storage systems. In the current course we introduce and motivate locally decodable codes, and discuss the central results of the subject. The course assumes basic familiarity with the properties of finite fields and is otherwise self-contained.
