Finding a majority ball with majority answers

DOI10.1016/j.endm.2015.06.047zbMath1386.68113arXiv1509.08276OpenAlexW2130922498MaRDI QIDQ322261

Dániel Gerbner, Balázs Keszegh, Dömötör Pálvölgyi, Balázs Patkós, Máté Vizer, Gábor Wiener

Publication date: 14 October 2016

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

zbMATH Keywords

search problemsmajorityplurality

Mathematics Subject Classification ID

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

Related Items

The minimum number of vertices in uniform hypergraphs with given domination number

Cites Work

• Determining the majority
• Computing majority with triple queries
• On computing majority by comparisons
• Variants of the majority problem.
• The quantum black-box complexity of majority
• Majority and plurality problems
• Probabilistic strategies for the partition and plurality problems
• Density-Based Group Testing
• Searching for majority with k-tuple queries
• Search for a majority element