73 citations · 634 across the 97 of their papers we have counts for
7 papers · 2 filters
Randomized Shellsort: A Simple Oblivious Sorting Algorithm
Michael T. Goodrich
In this paper, we describe randomized Shellsort--a simple, randomized, data-oblivious version of the Shellsort algorithm that always runs in O(n log n) time and, as we show, succee…
The Rainbow Skip Graph: A Fault-Tolerant Constant-Degree P2P Relay Structure
Michael T. Goodrich, Michael J. Nelson, Jonathan Z. Sun
We present a distributed data structure, which we call the rainbow skip graph. To our knowledge, this is the first peer-to-peer data structure that simultaneously achieves high fau…
Improved Adaptive Group Testing Algorithms with Applications to Multiple Access Channels and Dead Sensor Diagnosis
Michael T. Goodrich, Daniel S. Hirschberg
We study group-testing algorithms for resolving broadcast conflicts on a multiple access channel (MAC) and for identifying the dead sensors in a mobile ad hoc wireless network. In…
On the Approximability of Geometric and Geographic Generalization and the Min-Max Bin Covering Problem
Wenliang Du, David Eppstein, Michael T. Goodrich +1
We study the problem of abstracting a table of data about individuals so that no selection query can identify fewer than k individuals. We show that it is impossible to achieve arb…
On the Algorithmic Complexity of the Mastermind Game with Black-Peg Results
Michael T. Goodrich
In this paper, we study the algorithmic complexity of the Mastermind game, where results are single-color black pegs. This differs from the usual dual-color version of the game, bu…
Discrepancy-Sensitive Dynamic Fractional Cascading, Dominated Maxima Searching, and 2-d Nearest Neighbors in Any Minkowski Metric
Mikhail J. Atallah, Marina Blanton, Michael T. Goodrich +1
This paper studies a discrepancy-sensitive approach to dynamic fractional cascading. We provide an efficient data structure for dominated maxima searching in a dynamic set of point…
Learning Character Strings via Mastermind Queries, with a Case Study Involving mtDNA
Michael T. Goodrich
We study the degree to which a character string, , leaks details about itself any time it engages in comparison protocols with a strings provided by a querier, Bob, even if thos…