Query Complexity

Query complexity addresses issues like the number of calls to a black box routine, the number of queries to a data structure or the number of steps made by a parallel processor. It has immense applications, and not surprisingly a large number of papers have been written on it. Yet, currently there is no book that is entirely devoted to this subject. We fill this gap, and gather not only many valuable articles into a single book, but also organize knowledge, explain some key results, and giv...