  Estimating the condition numbers of random structured matrices is a well
known challenge, linked to the design of efficient randomized matrix
algorithms. We deduce such estimates for Gaussian random Toeplitz and circulant
matrices. The former estimates can be surprising because the condition numbers
grow exponentially in n as n grows to infinity for some large and important
classes of n-by-n Toeplitz matrices, whereas we prove the opposit for Gaussian
random Toeplitz matrices. Our formal estimates are in good accordance with our
numerical tests, except that circulant matrices tend to be even better
conditioned according to the tests than according to our formal study.
