The plurality problem with three colors and more.

DOI10.1016/J.TCS.2004.12.035MaRDI QIDQ557833zbMATH OpenOpenAlexFDO

Authors Martin Aigner, Gianluca De Marco, Manuela Montangero

Publication date 30 June 2005

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

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

zbMATH Keywords

Algorithm analysisCombinatorial searchGameMajority problem

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Analysis of algorithms (68W40) Search theory (90B40) Microeconomic theory (price theory and economic markets) (91B24) Combinatorial games (91A46)

Recommendations

• STACS 2004
• A plurality problem with three colors and query size three
• A note on the three color problem
• scientific article; zbMATH DE number 434910
• scientific article; zbMATH DE number 1500612
• scientific article; zbMATH DE number 5302772

Cites work

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

Cited in

(16)

• STACS 2005
• Adaptive majority problems for restricted query graphs and for weighted sets
• How to play the majority game with a liar
• Computing majority via multiple queries
• Randomized strategies for the plurality problem
• Probabilistic strategies for the partition and plurality problems
• The majority game with an arbitrary majority
• STACS 2004
• A plurality problem with three colors and query size three
• Finding non-minority balls with majority and plurality queries
• Computing and Combinatorics
• Adaptive majority problems for restricted query graphs and for weighted sets
• Searching for majority with \(k\)-tuple queries
• From discrepancy to majority
• Determining plurality
• Majority problems of large query size

This page was built for publication: The plurality problem with three colors and more.

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