Randomized and quantum query complexities of finding a king in a tournament

Mande, Nikhil ORCID: 0000-0002-9520-7340, Paraashar, Manaswi and Saurabh, Nitin (2023) Randomized and quantum query complexities of finding a king in a tournament. In: FSTTCS: Foundations of Software Technology and Theoretical Computer Science, 2023-12-18 - 2023-12-20, Hyderabad, India.

Text REF_Kings_FSTTCS23.pdf - Author Accepted Manuscript Download (752kB) | Preview

Abstract

A tournament is a complete directed graph. It is well known that every tournament contains at least one vertex v such that every other vertex is reachable from v by a path of length at most 2. All such vertices v are called kings of the underlying tournament. Despite active recent research in the area, the best-known upper and lower bounds on the deterministic query complexity (with query access to directions of edges) of finding a king in a tournament on n vertices are from over 20 years ago, and the bounds do not match: the best-known lower bound is O(n4/3) and the best-known upper bound is O(n3/2) [Shen, Sheng, Wu, SICOMP'03]. Our contribution is to show tight bounds (up to logarithmic factors) of eT(n) and eT(v n) in the randomized and quantum query models, respectively. We also study the randomized and quantum query complexities of finding a maximum out-degree vertex in a tournament.

Item Type:	Conference or Workshop Item (Unspecified)
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	27 Sep 2023 08:33
Last Modified:	17 Jan 2024 11:08
DOI:	10.4230/LIPIcs.FSTTCS.2023.30
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3173081