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

DOI10.4230/LIPICS.FSTTCS.2023.30MaRDI QIDQ6951703zbMATH OpenFDO

Authors Nikhil S. Mande, Manaswi Paraashar, Nitin Saurabh

Publication date 28 July 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.FSTTCS.2023.30

zbMATH Keywords

quantum computingquery complexityrandomized query complexitysearch problemstournament solutions

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Cites work

• An \(\Omega{} (n^{4/3})\) lower bound on the randomized complexity of graph properties
• Degree vs. approximate degree and Quantum implications of Huang’s sensitivity theorem
• Every vertex a king
• Finding kings in tournaments
• Finding Scores in Tournaments
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 1754599 (Why is no real title available?)
• scientific article; zbMATH DE number 2103524 (Why is no real title available?)
• Induced subgraphs of hypercubes and a proof of the sensitivity conjecture
• On recognizing graph properties from adjacency matrices
• Quantum approximate counting, simplified
• Quantum query complexity of minor-closed graph properties
• Quantum Query Complexity of Some Graph Problems
• Searching for Sorted Sequences of Kings in Tournaments
• Sorting and selection with imprecise comparisons
• Strengths and Weaknesses of Quantum Computing
• When you come at the king you best not miss

Cited in

(2)

• On the communication complexity of finding a king in a tournament
• From donkeys to kings in tournaments

This page was built for publication: Randomized and quantum query complexities of finding a king in a tournament

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6951703)