Randomized and Quantum Query Complexities of Finding a King in a Tournament

Nikhil S. Mande; Manaswi Paraashar; Nitin Saurabh

doi:10.4230/LIPIcs.FSTTCS.2023.30

Randomized and Quantum Query Complexities of Finding a King in a Tournament

Nikhil S. Mande^*, Manaswi Paraashar^*, Nitin Saurabh^*

^*Corresponding author for this work

Department of Mathematical Sciences

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

4 Downloads (Pure)

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.

Original language	English
Title of host publication	43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2023
Editors	Patricia Bouyer, Srikanth Srinivasan, Srikanth Srinivasan
Number of pages	19
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication date	2023
Article number	30
ISBN (Electronic)	9783959773041
DOIs	https://doi.org/10.4230/LIPIcs.FSTTCS.2023.30
Publication status	Published - 2023
Event	43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2023 - Hyderabad, India Duration: 18 Dec 2023 → 20 Dec 2023

Conference

Conference	43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2023
Country/Territory	India
City	Hyderabad
Period	18/12/2023 → 20/12/2023

Series	Leibniz International Proceedings in Informatics, LIPIcs
Volume	284
ISSN	1868-8969

Bibliographical note

Publisher Copyright:
© 2023 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

Keywords

quantum computing
Query complexity
randomized query complexity
search problems
tournament solutions

Access to Document

10.4230/LIPIcs.FSTTCS.2023.30Licence: CC BY

FulltextFinal published version, 814 KBLicence: CC BY

Cite this

Mande, N. S., Paraashar, M., & Saurabh, N. (2023). Randomized and Quantum Query Complexities of Finding a King in a Tournament. In P. Bouyer, S. Srinivasan, & S. Srinivasan (Eds.), 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2023 [30] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics, LIPIcs Vol. 284 https://doi.org/10.4230/LIPIcs.FSTTCS.2023.30

Randomized and Quantum Query Complexities of Finding a King in a Tournament. / Mande, Nikhil S.; Paraashar, Manaswi; Saurabh, Nitin.

43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2023. ed. / Patricia Bouyer; Srikanth Srinivasan; Srikanth Srinivasan. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023. 30 (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 284).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Mande, NS, Paraashar, M & Saurabh, N 2023, Randomized and Quantum Query Complexities of Finding a King in a Tournament. in P Bouyer, S Srinivasan & S Srinivasan (eds), 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2023., 30, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, LIPIcs, vol. 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2023, Hyderabad, India, 18/12/2023. https://doi.org/10.4230/LIPIcs.FSTTCS.2023.30

Mande NS, Paraashar M, Saurabh N. Randomized and Quantum Query Complexities of Finding a King in a Tournament. In Bouyer P, Srinivasan S, Srinivasan S, editors, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2023. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2023. 30. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 284). https://doi.org/10.4230/LIPIcs.FSTTCS.2023.30

Mande, Nikhil S. ; Paraashar, Manaswi ; Saurabh, Nitin. / Randomized and Quantum Query Complexities of Finding a King in a Tournament. 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2023. editor / Patricia Bouyer ; Srikanth Srinivasan ; Srikanth Srinivasan. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 284).

@inproceedings{e1f3eced4a8a4c8dabdb6054ca17ec6c,

title = "Randomized and Quantum Query Complexities of Finding a King in a Tournament",

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.",

keywords = "quantum computing, Query complexity, randomized query complexity, search problems, tournament solutions",

author = "Mande, {Nikhil S.} and Manaswi Paraashar and Nitin Saurabh",

note = "Publisher Copyright: {\textcopyright} 2023 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.; 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2023 ; Conference date: 18-12-2023 Through 20-12-2023",

year = "2023",

doi = "10.4230/LIPIcs.FSTTCS.2023.30",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

editor = "Patricia Bouyer and Srikanth Srinivasan and Srikanth Srinivasan",

booktitle = "43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2023",

}

TY - GEN

T1 - Randomized and Quantum Query Complexities of Finding a King in a Tournament

AU - Mande, Nikhil S.

AU - Paraashar, Manaswi

AU - Saurabh, Nitin

PY - 2023

Y1 - 2023

N2 - 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.

AB - 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.

KW - quantum computing

KW - Query complexity

KW - randomized query complexity

KW - search problems

KW - tournament solutions

U2 - 10.4230/LIPIcs.FSTTCS.2023.30

DO - 10.4230/LIPIcs.FSTTCS.2023.30

M3 - Article in proceedings

AN - SCOPUS:85180801472

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2023

A2 - Bouyer, Patricia

A2 - Srinivasan, Srikanth

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2023

Y2 - 18 December 2023 through 20 December 2023

ER -