BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1149
DTSTAMP:20230914T125952Z
SUMMARY:Fourier Analytic Techniques in Theoretical Computer Science
DESCRIPTION:Speaker: Somnath Chakraborty\n\nAbstract: \nIn this talk\, we w
 ill discuss the following problems.\n\nProblem 1\n"Suppose that $M$ is unk
 nown finite point set in $\\mathbb R^d$. Suppose $\\omega$ is some distrib
 ution on $M$\, and $\\gamma$ is the standard $d$-dimensional Gaussian. Let
  $X_\\omega$ and $X_\\gamma$ be independent random variables whose distrib
 utions are $\\omega$ and $\\gamma$\, respectively. Can we devise an effici
 ent randomized algorithm that\, given small $\\epsilon\,\\delta>0$\, and i
 ndependent random samples of $X_\\omega+X_\\gamma$\, outputs a distributio
 n $\\hat\\omega$ such that support of $\\hat\\omega$ is a finite point set
  $\\hat M$\, having same cardinality as $M$\, and within distance $\\epsil
 on$ from $M$\, and $\\sup_{m\\in M}|\\omega(m)-\\hat\\omega(\\pi(m))|$ is 
 `small' for some bijection $\\pi:M\\rightarrow\\hat M$\, with success prob
 ability at least $1-\\delta$?"\nProblem 2\n"Suppose that $M$ is a sphere o
 f dimension $d$\, and $\\mbox{Lip}_1(M)$ consists of all the Lipschitz fun
 ctions defined on $M$\, having Lipschitz constant at most 1. Can we devise
  an efficient randomized algorithm that\, given small $\\epsilon\,\\delta>
 0$\, for any input $\\phi\\in \\mbox{Lip}_1(M)$\, outputs a function $\\ha
 t\\phi$ on $M$\, such that $||\\hat\\phi-\\phi||_1\n
URL:https://www.tcs.tifr.res.in/web/events/1149
DTSTART;TZID=Asia/Kolkata:20210811T110000
DTEND;TZID=Asia/Kolkata:20210811T120000
END:VEVENT
END:VCALENDAR