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, on the other hand, are set systems where the pairwise intersection between any two sets coincides with the intersection among all of them.

This talk will discuss the relationship between relaxed versions of sunflowers - which we call daisies - and relaxed locally decodable codes. We highlight a recent lower bound for the size of these codes, obtained via a translation of any algorithm able to perform local decoding into the language of set systems. Current work (joint with Tom Gur and Oded Lachish) obtains an exponential improvement that nearly closes the gap to the upper bound achieved by state-of-the-art codes.