<p>I've been thinking about algorithms of the form where a quantity <span class="math-container">$c$</span> can be viewed as the expectation of some estimator (random variable) <span class="math-container">$X$</span> and the expectation is taken over some multivariate Gaussian, a formal way to maybe write this is
<span class="math-container">$$c = E_{\mathcal{N}(\mu, \Sigma)}[X]$$</span></p>
<p>The only one that I know of is this one <a href="https://arxiv.org/abs/1609.02416" rel="nofollow noreferrer">here</a> to estimate the permanent of a Hermitian positive semi-definite matrix. There they have access to <span class="math-container">$N$</span> samples and don't seem to factor the cost of obtaining the samples into the computation.</p>
<p>I'm curious if there are other &quot;well-known&quot; 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 <a href="https://cstheory.stackexchange.com/questions/8169/computational-complexity-of-random-sampling/8171#8171">question</a>.</p>

CC BY-SA 4.0
2022-09-27T05:01:31.467Z
The most famous Johnson-Lindenstrauss construction is probably the one using a matrix of i.i.d. Gaussians.
Yonatan N
CC BY-SA 4.0
2022-09-27T05:31:40.557Z
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.
smapers
CC BY-SA 4.0
2022-09-27T09:43:01.203Z
[The Gaussian mechanism in differential privacy.](https://en.wikipedia.org/wiki/Additive_noise_mechanisms#Gaussian_Mechanism)
Clement C.
CC BY-SA 4.0
2022-09-27T12:36:58.210Z
The Goemans-Williamson 0.878-approximation algorithm for Max-cut uses a random hyperplane, defined by its normal, a Gaussian vector.
GBathie
<ds.algorithms><reference-request><approximation-algorithms><randomized-algorithms>
Examples of Gaussian randomized algorithms
user135520
# Examples of Gaussian randomized algorithms

(Asked by: username_0 on 2022-09-26)

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](https://arxiv.org/abs/1609.02416) 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](https://cstheory.stackexchange.com/questions/8169/computational-complexity-of-random-sampling/8171#8171).

**Tags:** ds.algorithms, reference-request, approximation-algorithms, randomized-algorithms
> **Comments:**
> **username_1**: The most famous Johnson-Lindenstrauss construction is probably the one using a matrix of i.i.d. Gaussians.  
> **username_2**: 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.  
> **username_3**: [The Gaussian mechanism in differential privacy.](https://en.wikipedia.org/wiki/Additive_noise_mechanisms#Gaussian_Mechanism)  
> **username_4**: The Goemans-Williamson 0.878-approximation algorithm for Max-cut uses a random hyperplane, defined by its normal, a Gaussian vector.  

---

## 0 answers

