Finding a non-minority ball with majority answers

DOI10.1016/j.dam.2016.11.012zbMath1356.68158OpenAlexW2963356345MaRDI QIDQ505416

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

Publication date: 23 January 2017

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://real.mtak.hu/47414/1/1509.08276v2.pdf

zbMATH Keywords

medianmajoritycombinatorial search

Mathematics Subject Classification ID

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

Related Items (6)

Adaptive majority problems for restricted query graphs and for weighted sets ⋮ Majority problems of large query size ⋮ From discrepancy to majority ⋮ Finding non-minority balls with majority and plurality queries ⋮ A plurality problem with three colors and query size three ⋮ On non-adaptive majority problems of large query size

Cites Work

• Determining the majority
• Computing majority with triple queries
• On computing majority by comparisons
• Time bounds for selection
• Variants of the majority problem.
• The quantum black-box complexity of majority
• Majority and plurality problems
• The minimum number of vertices in uniform hypergraphs with given domination number
• Median Selection Requires $(2+\epsilon)n$ Comparisons
• Probabilistic strategies for the partition and plurality problems
• Density-Based Group Testing
• Searching for majority with k-tuple queries
• Search for a majority element

This page was built for publication: Finding a non-minority ball with majority answers