From discrepancy to majority

DOI10.1007/S00453-017-0303-7MaRDI QIDQ1751093zbMATH OpenOpenAlexFDO

Authors David Eppstein, Daniel S. Hirschberg

Publication date 23 May 2018

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.06488

zbMATH Keywords

algorithmslower boundsmajorityquery complexityset discrepancy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)

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/lfloorfrack2floor+O(k)$ queries, improving a previous method by De Marco and Kranakis that used $n-k+k^2/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 $lfloorn/kfloor$ by De Marco and Kranakis.

Recommendations

• From discrepancy to majority
• Computing majority with triple queries
• Majority problems of large query size
• Determining the majority
• Variants of the majority problem.

Cites work

• scientific article; zbMATH DE number 823957 (Why is no real title available?)
• Combinatorial pair testing: distinguishing workers from slackers
• Computing majority with triple queries
• Determining the majority
• Finding a non-minority ball with majority answers
• Improved Combinatorial Group Testing Algorithms for Real‐World Problem Sizes
• Majority problems of large query size
• Oblivious and adaptive strategies for the majority and plurality problems
• On computing majority by comparisons
• Probabilistic strategies for the partition and plurality problems
• Randomized strategies for the plurality problem
• Search for a majority element
• Searching for majority with \(k\)-tuple queries
• Short monotone formulae for the majority function
• The Average-Case Complexity of Determining the Majority
• The plurality problem with three colors and more.
• Variants of the majority problem.

Cited in

(10)

• On the decision tree complexity of threshold functions
• Adaptive majority problems for restricted query graphs and for weighted sets
• Finding non-minority balls with majority and plurality queries
• Determining the majority: The biased case
• Adaptive majority problems for restricted query graphs and for weighted sets
• On the Decision Tree Complexity of Threshold Functions
• Majority problems of large query size
• Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits
• On non-adaptive majority problems of large query size
• From discrepancy to majority

This page was built for publication: From discrepancy to majority

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1751093)