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<\epsilon$, with success probability at least $1-\delta$?"

The first problem requires that we find $\epsilon$-approximation of the centers of the underlying mixture of identical spherical gaussians, and good approximation of the weights. We do this in the regime when the number of centers is exponential in the dimension, using polynomially many computational steps (as a function of the number of centers). Such a bound was not known earlier.

For the second problem, we find a computationally efficient method of finding an equidistributed $\epsilon$-net on a $d$-dimensional sphere. The techniques are inspired by work of Landau-Russell (2004) which used ideas from Fourier analysis on finite groups to get a quantitative improvement on Alon-Roichman theorem that says a random Cayley graph is an expander.

These results are based on joint work with Hariharan Narayanan.