A tournament is a complete directed graph. A king in a tournament is a vertex v such that every other vertex is reachable from v via a path of length at most 2. It is well known that every tournament has at least one king, one of which is a maximum out-degree vertex. We study the communication complexity of these tasks in the most natural two-party distributed setting, where the edges of an underlying tournament are partitioned between two players. I will talk about some of our recent results for n-vertex tournaments:

 

1) The deterministic communication complexity of finding whether a source exists is ~Theta(log^2 n).

2) The deterministic and randomized communication complexities of finding a king are Theta(n).

3) The deterministic, randomized and quantum communication complexities of finding a maximum out-degree vertex are Theta(n log n), Theta(n log log n) and ~Theta(sqrt{n}), respectively.

 

Our upper bounds hold for all partitions of edges, and the lower bounds for a specific partition of the edges.

I will try to present ideas of proofs of some of our upper bounds and sketch the ideas that go into the lower bounds. This is based on joint work with Manaswi Paraashar, Swagato Sanyal and Nitin Saurabh.

 

Short Bio: 

Nikhil Mande is a Lecturer (Assistant Professor) in the Department of Computer Science at the University of Liverpool, a position he has held since January 2023. Previously, he was a postdoctoral researcher in the Algorithms and Complexity Group at CWI, hosted by Ronald de Wolf, until December 2022. Prior to that, he worked as a postdoctoral researcher in the Department of Computer Science at Georgetown University, under the mentorship of Justin Thaler. Nikhil completed his doctoral studies as a research scholar in the School of Technology and Computer Science at TIFR Mumbai, where he was advised by Arkadev Chattopadhyay.