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