Sunflowers, daisies and local codes

Abstract

Error-correcting codes are procedures that map messages (strings) to codewords (larger strings) in a way that makes the message recoverable even when the codeword is significantly corrupted. Codes that are locally decodable have additional structure: in order to recover a single character of the message, one need only read a small number of characters of the codeword. Combinatorial sunflowers are set systems where the pairwise intersection between any two sets coincides with the intersection among all of them. They have become objects of intense study, largely driven by the famous “sunflower conjecture” of Erdös and Rado.

This presentation will discuss two mathematical objects - daisies (a relaxation of combinatorial sunflowers) and relaxed locally decodable codes - and the relationship between them. We highlight recent lower bounds for the size of such codes, obtained via a translation of algorithms for local codes into the language of set systems.