Calendar

Coding theory is a central tool in communication, cryptography, algorithms, complexity, and more. Loosely speaking, codes are mathematical objects that provide means to endow information with structure that admits robustness to noise.

In recent years, there has been a surge of interest in highly structured codes that exhibit local-to-global phenomena. Such codes admit various types of algorithms that make their decisions based on a small local view, and thus run in sublinear time. In this talk, I will present recent results regarding two fundamental types of codes with a local-to-global structure: locally decodable codes and locally testable codes. In addition, I will discuss several applications of such codes to theoretical computer science and discrete mathematics, as well as discuss old open problems and new approaches for resolving them.