BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/356
DTSTAMP:20230914T125921Z
SUMMARY:A Survey on Uniform Hardness Amplification in NP
DESCRIPTION:Speaker: Sagnik  Mukhopadhyay\n\nAbstract: \nWe investigate the
  following question: If NP contains functions which are slightly hard to c
 ompute on average then does NP also contain function which is very hard to
  compute on average? Similar result is shown to hold outside NP by Yao by 
 his celebrated XOR lemma. But same technique breaks down to amplify the ha
 rdness inside NP.\n \nWe will restrict our attention to boolean function 
 though the result that we present can be generalized to functions that are
  not boolean valued. O'Donnell [OD02] showed hardness can be amplified in 
 NP in non-uniform setting and he amplified the hardness from $1/poly(n)$ t
 o $(1/2-1/n^{1/2+\\epsilon})$ for polynomial sized circuit. Healy et al [H
 VV04] extended this result and amplified the hardness to the optima.\n \n
 Trevisan in his papers [Tre03\, Tre05] amplified the hardness from $(1/pol
 y(n))$ to $(1/2 - 1/poly \\log (n))$ in uniform setting. The results of Tr
 evisan can be explained in terms of error correcting codes as done by Bure
 sh-Oppenheim et al [BKS06]. This\, in turn\, leads to the open question of
  finding a monotone code with efficient list decoding algorithm.\n \nIn t
 his talk\, we will describe the gradual development of hardness amplificat
 ion in NP.\n
URL:https://www.tcs.tifr.res.in/web/events/356
DTSTART;TZID=Asia/Kolkata:20130417T093000
DTEND;TZID=Asia/Kolkata:20130417T113000
LOCATION:AG-80
END:VEVENT
END:VCALENDAR