Standard
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. red. / Patricia Bouyer; Srikanth Srinivasan; Srikanth Srinivasan. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023. 30 (Leibniz International Proceedings in Informatics, LIPIcs, Bind 284).
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Harvard
Mande, NS
, Paraashar, M & Saurabh, N 2023,
Randomized and Quantum Query Complexities of Finding a King in a Tournament. i P Bouyer, S Srinivasan & S Srinivasan (red),
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, bind 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2023, Hyderabad, Indien,
18/12/2023.
https://doi.org/10.4230/LIPIcs.FSTTCS.2023.30APA
Mande, N. S.
, Paraashar, M., & Saurabh, N. (2023).
Randomized and Quantum Query Complexities of Finding a King in a Tournament. I P. Bouyer, S. Srinivasan, & S. Srinivasan (red.),
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 Bind 284
https://doi.org/10.4230/LIPIcs.FSTTCS.2023.30Vancouver
Mande NS
, Paraashar M, Saurabh N.
Randomized and Quantum Query Complexities of Finding a King in a Tournament. I Bouyer P, Srinivasan S, Srinivasan S, red., 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, Bind 284).
https://doi.org/10.4230/LIPIcs.FSTTCS.2023.30Author
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. red. / Patricia Bouyer ; Srikanth Srinivasan ; Srikanth Srinivasan. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023. (Leibniz International Proceedings in Informatics, LIPIcs, Bind 284).
Bibtex
@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",
}
RIS
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
N1 - Publisher Copyright:
© 2023 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.
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
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 -
