Computing majority with triple queries

DOI10.1016/J.TCS.2012.03.039MaRDI QIDQ690459zbMATH OpenOpenAlexFDO

Authors Gianluca De Marco, Evangelos Kranakis, Gábor Wiener

Publication date 27 November 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2012.03.039

zbMATH Keywords

searchpairing modelqueriesballscomputation modelscolorsgeneral model

Mathematics Subject Classification ID

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

Recommendations

• Computing majority with triple queries
• Searching for majority with \(k\)-tuple queries
• Finding a majority ball with majority answers
• Computing majority via multiple queries
• Finding a non-minority ball with majority answers

Cites work

• scientific article; zbMATH DE number 41347 (Why is no real title available?)
• Determining plurality
• Determining the majority
• Mathematical Foundations of Computer Science 2003
• Oblivious and adaptive strategies for the majority and plurality problems
• On computing majority by comparisons
• Optimization of Reduced Dependencies for Synchronous Sequential Machines
• Probabilistic strategies for the partition and plurality problems
• Randomized strategies for the plurality problem
• STACS 2004
• Search for a majority element
• The Average-Case Complexity of Determining the Majority
• Variants of the majority problem.

Cited in

(13)

• Adaptive majority problems for restricted query graphs and for weighted sets
• Finding non-minority balls with majority and plurality queries
• Computing majority via multiple queries
• The majority game with an arbitrary majority
• Adaptive majority problems for restricted query graphs and for weighted sets
• A plurality problem with three colors and query size three
• From discrepancy to majority
• Majority problems of large query size
• Finding a majority ball with majority answers
• Computing majority with triple queries
• Finding a non-minority ball with majority answers
• Triple-acyclicity in majorities based on difference in support
• Searching for majority with \(k\)-tuple queries

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 Q690459)