Consider a noisy linear observation model with an unknown permutation, based\non observing $y = \\Pi^* A x^* + w$, where $x^* \\in \\mathbb{R}^d$ is an unknown\nvector, $\\Pi^*$ is an unknown $n \\times n$ permutation matrix, and $w \\in\n\\mathbb{R}^n$ is additive Gaussian noise. We analyze the problem of permutation\nrecovery in a random design setting in which the entries of the matrix $A$ are\ndrawn i.i.d. from a standard Gaussian distribution, and establish sharp\nconditions on the SNR, sample size $n$, and dimension $d$ under which $\\Pi^*$\nis exactly and approximately recoverable. On the computational front, we show\nthat the maximum likelihood estimate of $\\Pi^*$ is NP-hard to compute, while\nalso providing a polynomial time algorithm when $d =1$.\n