Title: Limitations of non-uniform computational models
Abstract: 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.
Publication Year: 2002
Publication Date: 2002-01-01
Language: en
Type: article
Access and Citation
Cited By Count: 1
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot