Bernard Chazelle (Princeton University & NEC):
Nonmonotonicity in Geometric Searching
If there is one lesson to be learned from a quarter-century of research in multidimensional searching, it is that subtraction does not help: Whatever we can do with subtractions, we can do nearly as well with additions alone. It is tempting--maybe self-serving--to believe that this is not simply an accumulation of evidence but the actual truth, because this would essentially close the book on the subject. Indeed, nearly all nonmonotone bounds are tight: a triumph of complexity theory!
In this talk, I will explain why the celebration might be a little premature. I will give new evidence of some natural instances of multidimensional searching where the monotone and nonmonotone complexities provably differ. How much of our current picture of multidimensional searching will eventually unravel is the main open question.
I will briefly review some of the standard lower bound techniques in the field, some of which are mathematically very beautiful. This talk will require no knowledge of computational geometry.