Skip to content Search
Search our website:

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.