Limitations of non-uniform computational models

The demonstration of a limitation on the abilities of a computational model is a central theme in complexity theory. Hardness results, which demonstrate such limitations, are crucial for complexity theory's efforts to classify problems into classes based on their inherent difficulty.; In this work, we discuss three well-studied models of computation and prove hardness results in each of them. The models studied here share the common feature of nonuniformity.; First, we study the complexity of the well-known problem of high dimensional approximate nearest neighbour searching in the cell probe model. We establish the first nontrivial lower bound on the complexity of this problem.; We then turn to the Boolean decision tree model and study what is arguably the most famous open problem in the model: Karp's Evasiveness Conjecture for graph properties. We make partial progress towards a settlement of this conjecture. We prove that the conjecture holds for all minor-closed graph properties and improve upon the best previously known results for subgraph containment and related properties.; Finally, we study the direct sum question in the simultaneous message model of communication. We show that the complexity of the equality function satisfies a direct sum theorem in this model: to solve m different equality problems one needs m times as many bits of communication as for one problem. We also prove some related results and generalisations.