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 Item (Unspecified)
Uncontrolled Keywords:	Query complexity, quantum computing, randomized query complexity, tournament solutions, search problems
Divisions:	Faculty of Science & Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	27 Sep 2023 08:33
Last Modified:	23 May 2026 07:54
DOI:	10.4230/LIPIcs.FSTTCS.2023.30
Related Websites:	Author
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3173081
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.