BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1485
DTSTAMP:20241108T062250Z
SUMMARY:A High-Dimensional Goldreich-Levin Theorem
DESCRIPTION:Speaker: Silas Richelson (University of California\, Riverside)
 \n\nAbstract: \nIn this work we prove a high dimensional analogue of the b
 eloved Goldreich-Levin theorem (STOC 1989)\, which is the first local list
 -decoding algorithm. We consider the following algorithmic problem: given 
 oracle access to a function $f: Z_q^m \\rightarrow Z_q^n$ such that $\\Pr_
 {x \\sim Z_q^m} [ f(x)=Ax ] \\geq \\epsilon$ for some matrix $A \\in Z_q^{
 n \\times m}$ and $\\epsilon>0$\, recover $A$ (or a list of all such matri
 ces).\nThe original Goldreich-Levin theorem (which handles the case $n=1$ 
 above) actually handles the agreements $\\epsilon \\gt 1/q$ for any $n$. H
 ence\, we focus on tiny agreements $\\epsilon \\leq 1/q$. As stated\, this
  problem cannot be efficiently solved\, since when the list of matrices $A
 $ with good agreement with $f$ might be exponentially large. Thus we defin
 e a new notion of list-decoding\; a short list of such matrices "capturing
 '' all others.\nOur main theorem gives an algorithm which efficiently reco
 vers a (small) list\, of size $O( \\epsilon^{-1} )$\, of linear maps $A$ w
 hich satisfy: (1) each $A$ good agreement with $f$\, and (2) every linear 
 map which has good agreement with $f$\, also has good agreement with some 
 map $A$ in our list. The proof makes novel use of Fourier analysis.\nShort
  Bio:\nSilas Richelson is an Assistant Professor in the CSE Department at
  UC Riverside. His research interests are in Cryptography\, Computer Secur
 ity and Complexity Theory. He got his Ph. D. in 2014 from UCLA under the s
 upervision of Rafail Ostrovsky. From 2015 to 2017 he was a postdoctoral re
 searcher with a joint appointment at the MIT CSAIL and BU Computer Scie
 nce departments\, working with Vinod Vaikuntanathan and Ran Canetti.\n
URL:https://www.tcs.tifr.res.in/web/events/1485
DTSTART;TZID=Asia/Kolkata:20241113T100000
DTEND;TZID=Asia/Kolkata:20241113T110000
LOCATION:via Zoom in A201
END:VEVENT
END:VCALENDAR