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
