Cache-oblivious orthogonal range searching. |
Cache-oblivious sorting. |
An experimental analysis of dynamic all pairs shortest paths algorithms. |
Some issues regarding peer to peer networks. |
Competitive auctions. (Joint work with Amos Fiat, Jason Hartline, Anna Karlin, Andrew Wright) |
Efficient implicit data structures for the dictionary problem. (The results presented here are based on joint papers with Gianni Franceschini and on a paper with Gianni Franceschini, Ian Munro and Linda Pagli) |
Input-sensitive data structures. (Joint work with Erik Demaine) |
Inverse range searching with priorities. (Joint work with Eyal Molad and Robert E. Tarjan) |
Complexity of Reconstructing Phylogenetic Trees. |
A new approach to dynamic all pairs shortest paths. |
Pattern discovery in nucleotide sequences: methods and data structures.
|
Internet packet filtering on any number of attributes via multi-dimensional
point stabbing. Here we show that the same asymptotic complexity bound holds for any fixed number d of attributes. Moreover the data structure is dynamic and has low preprocessing time. As a corollary of the techniques used, we also show that, under the same general assumptions, orthogonal range counting queries over a set of n points with bounded integer coordinates can be answered in time O(1) in any fixed dimension d using storage O(n^{1+epsilon}). |
Using multi-level graphs for fast single-pair shortest-path computation. |