  We study Crystal Structure Prediction, one of the major problems in
computational chemistry. This is essentially a continuous optimization problem,
where many different, simple and sophisticated, methods have been proposed and
applied. The simple searching techniques are easy to understand, usually easy
to implement, but they can be slow in practice. On the other hand, the more
sophisticated approaches perform well in general, however almost all of them
have a large number of parameters that require fine tuning and, in the majority
of the cases, chemical expertise is needed in order to properly set them up. In
addition, due to the chemical expertise involved in the parameter-tuning, these
approaches can be {\em biased} towards previously-known crystal structures. Our
contribution is twofold. Firstly, we formalize the Crystal Structure Prediction
problem, alongside several other intermediate problems, from a theoretical
computer science perspective. Secondly, we propose an oblivious algorithm for
Crystal Structure Prediction that is based on local search. Oblivious means
that our algorithm requires minimal knowledge about the composition we are
trying to compute a crystal structure for. In addition, our algorithm can be
used as an intermediate step by {\em any} method. Our experiments show that our
algorithms outperform the standard basin hopping, a well studied algorithm for
the problem.
