From Discrepancy to Majority

David Eppstein, Daniel S. Hirschberg

We show how to select an item with the majority color from $n$ two-colored items, given access to the items only through an oracle that returns the discrepancy of subsets of $k$ it…