Computing majority with triple queries
From MaRDI portal
Publication:3087986
DOI10.1007/978-3-642-22685-4_52zbMATH Open1353.68292arXiv1105.1622OpenAlexW1515035281MaRDI QIDQ3087986FDOQ3087986
Authors: Gábor Wiener, Gianluca De Marco, Evangelos Kranakis 
Publication date: 17 August 2011
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Abstract: Consider a bin containing balls colored with two colors. In a -query, balls are selected by a questioner and the oracle's reply is related (depending on the computation model being considered) to the distribution of colors of the balls in this -tuple; however, the oracle never reveals the colors of the individual balls. Following a number of queries the questioner is said to determine the majority color if it can output a ball of the majority color if it exists, and can prove that there is no majority if it does not exist. We investigate two computation models (depending on the type of replies being allowed). We give algorithms to compute the minimum number of 3-queries which are needed so that the questioner can determine the majority color and provide tight and almost tight upper and lower bounds on the number of queries needed in each case.
Full work available at URL: https://arxiv.org/abs/1105.1622
Recommendations
Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Nonnumerical algorithms (68W05)
Cited In (9)
- Computing majority via multiple queries
- Triple-acyclicity in majorities based on difference in support
- From discrepancy to majority
- Computing majority with triple queries
- Finding a majority ball with majority answers
- On non-adaptive majority problems of large query size
- Searching for majority with \(k\)-tuple queries
- From discrepancy to majority
- Majority problems of large query size
This page was built for publication: Computing majority with triple queries
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3087986)
