Randomized and Quantum Query Complexities of Finding a King in a Tournament
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Dokumenter
- Fulltext
Forlagets udgivne version, 814 KB, PDF-dokument
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.
Originalsprog | Engelsk |
---|---|
Titel | 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2023 |
Redaktører | Patricia Bouyer, Srikanth Srinivasan, Srikanth Srinivasan |
Antal sider | 19 |
Forlag | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Publikationsdato | 2023 |
Artikelnummer | 30 |
ISBN (Elektronisk) | 9783959773041 |
DOI | |
Status | Udgivet - 2023 |
Begivenhed | 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2023 - Hyderabad, Indien Varighed: 18 dec. 2023 → 20 dec. 2023 |
Konference
Konference | 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2023 |
---|---|
Land | Indien |
By | Hyderabad |
Periode | 18/12/2023 → 20/12/2023 |
Navn | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Vol/bind | 284 |
ISSN | 1868-8969 |
Bibliografisk note
Publisher Copyright:
© 2023 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.
ID: 390880146