Alladi Ramakrishnan Hall

Complexity of Finding a King in a Tournament

Nitin Saurabh

A tournament is a complete graph such that there is a directed edge between any pair of vertices.
A vertex v is called a king in a tournament if every other vertex is reachable from v by a path of length at most 2.
Given an unknown tournament how many edge directions does one need to know to output a king in the given tournament?
In this talk we will explore this problem and its variants.
We will present several tight bounds for this problem in query and communication models in deterministic, randomized and quantum settings.

The talk will be based on the following works:
1) Randomized and Quantum Query Complexities of Finding a King in a Tournament (FSTTCS 2023)
joint work with Nikhil Mande (University of Liverpool) and Manaswi Paraashar (University of Copenhagen)

2) On the Communication Complexity of Finding a King in a Tournament (Manuscript)
joint work with Nikhil Mande (University of Liverpool), Manaswi Paraashar (University of Copenhagen), and Swagato Sanyal (IIT Kharagpur)