Master’s Thesis Presentation • Algorithms and Complexity • A Las Vegas Algorithm for the Ordered Majority Problem

Monday, September 19, 2022 1:30 pm - 2:30 pm EDT (GMT -04:00)

Please note: This master’s thesis presentation will take place online.

Ben Baral, Master’s candidate
David R. Cheriton School of Computer Science

Supervisor: University Professor J. Ian Munro

In this thesis, we study the majority problem using ordered comparisons under the Las Vegas randomized algorithm model. The majority problem asks whether a given set of n elements, each with some colour, has a colour which appears on more than half of the elements. We focus on algorithms for this problem whose fundamental operation is to compare two elements, and in particular the comparison returns one of {<, =, >}. Additionally, we are interested specifically in Las Vegas randomized algorithms for this problem, which solve the problem correctly in all cases but whose running time is a random variable. Interestingly, most previous work studying this problem considers a different model where comparisons return just whether two elements are equal or not, instead of providing ordered information.

Our contribution is a novel Las Vegas algorithm that uses only n + o(n) comparisons in the expectation, compared to 7n/6 + o(n) comparisons required in the expectation by the previous best algorithm for this problem.


To join this master’s thesis presentation on Zoom, please go to https://uwaterloo.zoom.us/j/96426812538?pwd=WSt6TE1lQysrZjk2UTl5SjRBUmhFdz09.