Seminars & Colloquia Calendar

Download as iCal file

Discrete Math

Locally decodable codes and arithmetic progressions in random settings

Sivakanth Gopi, Microsoft Research

Location:  Hill 705
Date & time: Monday, 15 October 2018 at 2:00PM - 3:00PM


(1) A set D of natural numbers is called t-intersective if every positive upper density subset A of natural numbers contains a (t+1)-length arithmetic progression (AP) whose common differences is in D. Szemeredi's theorem states that the set of all natural numbers is t-intersective for every t. But there are other non-trivial examples like {p-1: p prime}, {1^k,2^k,3^k,dots} for any k etc. which are t-intersective for every t. A natural question to study is at what density random subsets of natural numbers become t-intersective? 

(2) Let X_t be the number of t-APs in a random subset of Z/NZ where each element is selected with probability p independently. Can we prove precise estimates on the probability that X_t is much larger than its expectation? 

(3) Locally decodable codes (LDCs) are error correcting codes which allow ultra fast decoding of any message bit from a corrupted encoding of the message. What is the smallest encoding length of such codes? 
These seemingly unrelated problems can be addressed by studying the Gaussian width of images of low degree polynomial mappings, which seems to be a fundamental tool applicable to many such problems. Adapting ideas from existing LDC lower bounds, we can prove a general bound on Gaussian width of such sets which reproves the known LDC lower bounds and also implies new bounds for the above mentioned problems. Our bounds are still far from conjectured bounds which suggests that there is plenty of room for improvement. If time permits, we will discuss connections to type constants of injective tensor products of Banach spaces (or chernoff bounds for tensors in simpler terms).

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.