Estimation of the covariance matrix of a p-dimensional probability distribution is a basic problem in statistics. A classical estimator is the sample covariance matrix, obtained from a sample of n independent points. The more classical regime and well studied regime is where n > p. We conjecture that n = O(p) suffices to accurately estimate the covariance matrix of arbitrary distribution with finite 4-th moments. We discuss some recent progress on this problem, which has a connection to the "Levy flight", a heavy-tailed Brownian motion that exhibits sporadic huge jumps (similar to a predator's path looking for prey). The other regime, n < p, has recently become quite popular in statistics and its various applications (e.g. genomics) because of limiting sampling capacities compared with huge dimensions. We will discuss the problem and recent progress in this regime as well.