BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1428
DTSTAMP:20240522T041810Z
SUMMARY:Local Correction of Linear Functions over the Boolean Cube
DESCRIPTION:Speaker: Madhu Sudan (Harvard John A. Paulson School of Enginee
 ring and Applied Sciences)\n\nAbstract: \nSince the late 1980's it has bee
 n known that low-degree multivariate polynomials over finite fields form "
 locally correctible codes". In other words\, given oracle access to a func
 tion f:F^n -> F such there is a degree d polynomial P(X1...Xn) whose evalu
 ation agree with f on all but a tiny fraction of points\, and an arbitrary
  point b in F^n\, it is possible to determine P(b) with high probability 
 while querying f in a constant number of points (where the number of queri
 es depends on the degree d\, but not the number of variables n).Of course 
 this result doesn't work for infinite fields since then one has to define 
 a measure over F^n. But can one hope for a similar result for f:S^n \\to F
  for some finite subset S of F? In a previous work with Bafna and Srinivas
 an we had shown that any such local decoding result (over say the reals or
  rationals) would require roughly Omega-tilde(\\log n) queries (even when 
 d = 1).In this talk we describe a complementary result that shows that O-t
 ilde(\\log n) queries suffice in the linear (d=1) case when S = {0\,1} (ov
 er any field F\, and indeed any abelian group G). Working over sets like S
 ^n provides novel challenges due to the fact that the most handy tool in p
 revious works\, namely affine-invariance of the domain\, is no longer avai
 lable. Our local reconstruction algorithms rely centrally on the ability t
 o construct a small set of nearly balanced vectors in {-1\,1}^n whose span
  contains 1^n. Combined with a double dose of hypercontractivity this lead
 s to a local algorithm correcting up to 1/4  fraction of errors. Our fina
 l result gives a list-decoding algorithm correcting nearly 50% errors. Her
 e the key ingredient is the combinatorial bound on the list size which we 
 prove using a kitchen sink of techniques that show large lists must contai
 n many sparse polynomials and then ruling out such possibilities which inv
 olves case analysis depending on the group G.\nJoint work with Prashanth A
 mireddy\, Amik Raj Behera\, Manaswi Paraashar\, and Srikanth Srinivasan.\n
URL:https://www.tcs.tifr.res.in/web/events/1428
DTSTART;TZID=Asia/Kolkata:20240528T140000
DTEND;TZID=Asia/Kolkata:20240528T150000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR