Average-case versus worst-case complexity of computation

Two natural notions of hardness of computational problems are worst-case hardness which measures how hard the hardest instance of a problem is, and average-case hardness which is a measure of how hard it is to solve a randomly given instance. While the former is the more traditional notion, it might be argued that it is the latter that truly captures the complexity of the problem. From a cryptographic viewpoint too, it is the average-case complexity that is important.; This dissertation studies the connection between the two notions of complexity for specific problems, particularly ones involving lattices. The most important such problem is the Shortest Vector Problem (SVP): Given a lattice, compute a shortest non-zero vector in it. We improve upon a result of Miklós Ajtai who proved that the average-case hardness of this problem over a certain class of lattices was equivalent to the worst-case hardness of other lattice problems. Since these latter problems are thought to be hard in the worst-case, this says that the SVP on that class is hard on average. This is significant for the security of a future cryptosystem based on the SVP. We also present a worst-case hardness result for the SVP, proving that it is NP-hard to find an approximately short vector in a given lattice.; A graph-theoretic application of lattices is also shown. The graphs considered are called circulant graphs and the problem is to find a shortest loop in such a graph. With every circulant graph is associated a lattice and finding a shortest loop in the graph is the same as finding a shortest vector in the lattice. This enables us to apply lattice techniques to study the complexity of this problem.; Finally, moving away from lattices, we show that a hierarchy exists for a probabilistic complexity class under certain hardness assumptions. The assumptions are worst-case, but for a hierarchy theorem to be proved, average-case hardness is required. We make use of standard techniques to effect the conversion. This once again underlines the usefulness of a connection between these two kinds of computational complexity.