Title: Sunflowers, daisies and local codes
- Speaker: Marcel de Sena Dall'Agnol. Department of Computer Science, University of Warwick.
- Date: Tuesday, 26 November 2019 from 16:00 to 17:00
- Location: Room 151
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.