# Examples of Gaussian randomized algorithms

I've been thinking about algorithms of the form where a quantity $$c$$ can be viewed as the expectation of some estimator (random variable) $$X$$ and the expectation is taken over some multivariate Gaussian, a formal way to maybe write this is $$c = E_{\mathcal{N}(\mu, \Sigma)}[X]$$

The only one that I know of is this one here to estimate the permanent of a Hermitian positive semi-definite matrix. There they have access to $$N$$ samples and don't seem to factor the cost of obtaining the samples into the computation.

I'm curious if there are other "well-known" examples of randomized algorithms where the randomness comes from a Gaussian distribution? I'm curious about how other algorithms factor the cost of obtaining samples into their time complexity. This question is somewhat addressed in this older question.

• The most famous Johnson-Lindenstrauss construction is probably the one using a matrix of i.i.d. Gaussians. Sep 27 at 5:01
• There's some Markov chain algorithms, such as the Langevin algorithm or Hamiltonian Monte Carlo, in which the random steps are chosen based on a Gaussian. Sep 27 at 5:31
• The Gaussian mechanism in differential privacy. Sep 27 at 9:43
• The Goemans-Williamson 0.878-approximation algorithm for Max-cut uses a random hyperplane, defined by its normal, a Gaussian vector.
– GBat
Sep 27 at 12:36