How many matches does it take to find a champion?
April 25 @ 12:00 pm - 5:00 pm
Speaker: Neeldhara Misra
Abstract: Suppose there are n horses and we have a track with k lanes. If we pick k horses to run a race, a linear ordering is established among the chosen horses, based only on the finishing order (race time is not considered). How many races do we need to organize to determine the best two horses? How many races are necessary to reveal the full ranking?
To address this question, we might assume that there is an overall linear ordering among all horses and that the outcomes of the races are always consistent with this global linear order. However, this may not be true in real-world tournaments: actual outcomes may deviate from our estimate of the global order. In this talk, we will discuss some developments around questions of determining the “top k” elements in the general setting of tournaments and the special situation when we are promised that comparisons are consistent with an underlying linear order.
The results presented are drawn from the following papers:
Variations on the Tournament Problem
Fabrizio Luccio, Linda Pagli, Nicola Santoro
Fabrizio Luccio, Linda Pagli, Nicola Santoro
FUN 2024
Arnab Maiti, Palash Dey
TCS 2024
Short bio: Neeldhara Misra is a Smt. Amba and Sri. V S Sastry Chair Associate Professor of Computer Science and Engineering at the Indian Institute of Technology, Gandhinagar. She completed her PhD from the Institute for Mathematical Sciences in 2012 in Theoretical Computer Science. Her research interests include the design and analysis of algorithms and computational social choice. She is also interested in visualizations and other methods to communicate computational thinking at an elementary level. She also enjoys learning about new card tricks, especially self-working ones — even though she can’t remember any!
https://www.neeldhara.com/
https://www.neeldhara.com/