64 citations · 112 across the 6 of their papers we have counts for
6 papers
The Marco Polo Problem: A Combinatorial Approach to Geometric Localization
Ofek Gila, Michael T. Goodrich, Zahra Hadizadeh +2
We introduce and study the Marco Polo problem, which is a combinatorial approach to geometric localization. In this problem, we are told there are one or more points of interest (P…
From Discrepancy to Majority
David Eppstein, Daniel S. Hirschberg
We show how to select an item with the majority color from two-colored items, given access to the items only through an oracle that returns the discrepancy of subsets of it…
Combinatorial Pair Testing: Distinguishing Workers from Slackers
David Eppstein, Michael T. Goodrich, Daniel S. Hirschberg
We formalize a problem we call combinatorial pair testing (CPT), which has applications to the identification of uncooperative or unproductive participants in pair programming, mas…
Fully De-Amortized Cuckoo Hashing for Cache-Oblivious Dictionaries and Multimaps
Michael T. Goodrich, Daniel S. Hirschberg, Michael Mitzenmacher +1
A dictionary (or map) is a key-value store that requires all keys be unique, and a multimap is a key-value store that allows for multiple values to be associated with the same key.…
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…
Improved Combinatorial Group Testing Algorithms for Real-World Problem Sizes
David Eppstein, Michael T. Goodrich, Daniel S. Hirschberg
We study practically efficient methods for performing combinatorial group testing. We present efficient non-adaptive and two-stage combinatorial group testing algorithms, which ide…