Tata Institute of Fundamental Research
Fourier Analytic Techniques in Theoretical Computer Science
Synopsis Seminar
Speaker:
Somnath Chakraborty
Organiser:
Prahladh Harsha
Date:
Wednesday, 11 Aug 2021, 11:00 to 12:00
Venue:
(Scan to add to calendar)
Abstract:
In this talk, we will discuss the following problems.
Problem 1
"Suppose that $M$ is unknown finite point set in $\mathbb R^d$. Suppose $\omega$ is some distribution on $M$, and $\gamma$ is the standard $d$-dimensional Gaussian. Let $X_\omega$ and $X_\gamma$ be independent random variables whose distributions are $\omega$ and $\gamma$, respectively. Can we devise an efficient randomized algorithm that, given small $\epsilon,\delta>0$, and independent random samples of $X_\omega+X_\gamma$, outputs a distribution $\hat\omega$ such that support of $\hat\omega$ is a finite point set $\hat M$, having same cardinality as $M$, and within distance $\epsilon$ 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 probability at least $1-\delta$?"
Problem 2
"Suppose that $M$ is a sphere of dimension $d$, and $\mbox{Lip}_1(M)$ consists of all the Lipschitz functions 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 $\hat\phi$ on $M$, such that $||\hat\phi-\phi||_1
| Speaker: | Somnath Chakraborty |
| Organiser: | Prahladh Harsha |
| Date: | Wednesday, 11 Aug 2021, 11:00 to 12:00 |
| Venue: |
(Scan to add to calendar)
Abstract:
In this talk, we will discuss the following problems.
Problem 1
"Suppose that $M$ is unknown finite point set in $\mathbb R^d$. Suppose $\omega$ is some distribution on $M$, and $\gamma$ is the standard $d$-dimensional Gaussian. Let $X_\omega$ and $X_\gamma$ be independent random variables whose distributions are $\omega$ and $\gamma$, respectively. Can we devise an efficient randomized algorithm that, given small $\epsilon,\delta>0$, and independent random samples of $X_\omega+X_\gamma$, outputs a distribution $\hat\omega$ such that support of $\hat\omega$ is a finite point set $\hat M$, having same cardinality as $M$, and within distance $\epsilon$ 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 probability at least $1-\delta$?"
Problem 2
"Suppose that $M$ is a sphere of dimension $d$, and $\mbox{Lip}_1(M)$ consists of all the Lipschitz functions 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 $\hat\phi$ on $M$, such that $||\hat\phi-\phi||_1
Problem 1
"Suppose that $M$ is unknown finite point set in $\mathbb R^d$. Suppose $\omega$ is some distribution on $M$, and $\gamma$ is the standard $d$-dimensional Gaussian. Let $X_\omega$ and $X_\gamma$ be independent random variables whose distributions are $\omega$ and $\gamma$, respectively. Can we devise an efficient randomized algorithm that, given small $\epsilon,\delta>0$, and independent random samples of $X_\omega+X_\gamma$, outputs a distribution $\hat\omega$ such that support of $\hat\omega$ is a finite point set $\hat M$, having same cardinality as $M$, and within distance $\epsilon$ 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 probability at least $1-\delta$?"
Problem 2
"Suppose that $M$ is a sphere of dimension $d$, and $\mbox{Lip}_1(M)$ consists of all the Lipschitz functions 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 $\hat\phi$ on $M$, such that $||\hat\phi-\phi||_1