The Average-Case Complexity of Determining the Majority
DOI10.1137/S0097539794275914zbMATH Open0868.68066OpenAlexW1971578319MaRDI QIDQ4337428FDOQ4337428
Authors: L. Alonso, Edward M. Reingold, R. Schott 
Publication date: 3 August 1997
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539794275914
Recommendations
Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Searching and sorting (68P10) Factorials, binomial coefficients, combinatorial functions (05A10) Radix representation; digital problems (11A63) Parallel algorithms in computer science (68W10)
Cited In (23)
- Average-case lower bounds for the plurality problem
- How to play the majority game with a liar
- Computing majority via multiple queries
- Tight bounds on plurality
- Randomized strategies for the plurality problem
- Randomized algorithms for the majority problem
- Truth tellers and liars with fewer questions
- The plurality problem with three colors and more.
- Determining the majority
- Computing majority with triple queries
- Search for a majority element
- The worst-case chip problem
- Variants of the majority problem.
- Searching for majority with k-tuple queries
- Title not available (Why is that?)
- Finding modes with equality comparisons
- On approximate majority and probabilistic time
- On randomized algorithms for the majority problem
- New applications of the incompressibility method. II
- Determining the majority: The biased case
- From discrepancy to majority
- Analysis of Boyer and Moore's \texttt{MJRTY} algorithm
- Finding Mode Using Equality Comparisons
This page was built for publication: The Average-Case Complexity of Determining the Majority
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4337428)
