Dominique Tschopp, Ph.D., 2009
Thesis director: Prof. S N. Diggavi Thesis co-director: Prof. M. Grossglauser
- Prof. J-Y. Le Boudec (EPFL)
- Prof. M. Mitzenmacher (Harvard)
- Prof. S. Shakkottai (University of Texas, Austin)
- Prof. E. Telatar (EPFL, Committee president).
Dominique tacked two problems related to design and analysis of algorithms. The first was on routing on wireless networks and the second was on nearest neighbot search through comparisons. The routing algorithm was among the first developed for dynamic wireless networks where explicitly the trade-off between routing efficiency and control overhead was quantified (provably). This led to a nice connection between wireless networks represented by variants of geometric random graphs and doubling metric spaces. The second part of the thesis developed algorithms with (provable) performance for nearest neighbor search when only comparison information was available. This led to a new concept of “rank-sensitive” hashing which was designed to capture similarities in comparisons rather than metric distances.