From Discrepancy to Majority

2015/12/21 by David Eppstein, Daniel S. Hirschberg
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Mathematical Approximation and Integration #Monochromatic color #Oracle #Partition (number theory) #Theory of computation #Upper and lower bounds #cs.DS

paper · pdf · doi:10.1007/s00453-017-0303-7

published as Algorithmica 80 (4): 1278-1297, 2018 · 15 pages, 3 figures. Extended version of a paper to appear at LATIN 2016

arxiv created 2015/12/21 · openalex publication_date 2017/03/16 · openalex created_date 2017/03/23 · arxiv updated 2018/03/01 · openalex updated_date 2026/08/06

Abstract

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 items. We use n/\lfloor\tfrack2\rfloor+O(k) queries, improving a previous method by De Marco and Kranakis that used n-k+k²/2 queries. We also prove a lower bound of n/(k-1)-O(n^1/3) on the number of queries needed, improving a lower bound of \lfloor n/k\rfloor by De Marco and Kranakis.

Citations

• Short monotone formulae for the majority function