Cover Image

On the communication complexity of finding a king in a tournament

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Mande, Nikhil S., Paraashar, Manaswi, Sanyal, Swagato, Saurabh, Nitin
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity Quantum Physics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Quantum Search With Generalized Wildcards
by: Cornelissen, Arjan, et al.
Published: (2025)

Lower bounds for quantum-inspired classical algorithms via communication complexity
by: Mande, Nikhil S., et al.
Published: (2024)

Approximate Degree Composition for Recursive Functions
by: Chakraborty, Sourav, et al.
Published: (2024)

Tight Bounds for Quantum Phase Estimation and Related Problems
by: Mande, Nikhil S., et al.
Published: (2023)

Complexity of learning matchings and half graphs via edge queries
by: Mande, Nikhil S., et al.
Published: (2025)

Improved Quantum Query Upper Bounds Based on Classical Decision Trees
by: Cornelissen, Arjan, et al.
Published: (2022)

Separations between Combinatorial Measures for Transitive Functions
by: Chakraborty, Sourav, et al.
Published: (2021)

Bounds for Hardness Condensation in the Query Model
by: Kayal, Chandrima, et al.
Published: (2026)

Magic and communication complexity
by: Girish, Uma, et al.
Published: (2025)

Instance complexity of Boolean functions
by: Liu, Alison Hsiang-Hsuan, et al.
Published: (2023)

Randomized query composition and product distributions
by: Sanyal, Swagato
Published: (2024)

Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions
by: Datta, Swarnalipa, et al.
Published: (2023)

Quantum Sabotage Complexity
by: Cornelissen, Arjan, et al.
Published: (2024)

Query Complexity with Unknowns
by: Mande, Nikhil S., et al.
Published: (2024)

Local Correction of Linear Functions over the Boolean Cube
by: Amireddy, Prashanth, et al.
Published: (2024)

Low Degree Local Correction Over the Boolean Cube
by: Amireddy, Prashanth, et al.
Published: (2024)

Distributed inner product estimation with limited quantum communication
by: Arunachalam, Srinivasan, et al.
Published: (2024)

Hardness of Finding Kings and Strong Kings
by: Alaoui, Ziad Ismaili, et al.
Published: (2025)

Quantum computational complexity of matrix functions
by: Cifuentes, Santiago, et al.
Published: (2024)

Computational complexity of isometric tensor network states
by: Malz, Daniel, et al.
Published: (2024)

Direct sum theorems beyond query complexity
by: Suruga, Daiki
Published: (2024)

Separations in query complexity for total search problems
by: Ben-David, Shalev, et al.
Published: (2024)

On the success probability of quantum order finding
by: Ekerå, Martin
Published: (2022)

On query complexity measures and their relations for symmetric functions
by: Mittal, Rajat, et al.
Published: (2021)

Quantum and classical query complexities of functions of matrices
by: Montanaro, Ashley, et al.
Published: (2023)

Physical complexity and black hole quantum computers
by: Reilly, Michele, et al.
Published: (2025)

On the complexity of unique quantum witnesses and quantum approximate counting
by: Anshu, Anurag, et al.
Published: (2024)

On the complexity of estimating ground state entanglement and free energy
by: Gharibian, Sevag, et al.
Published: (2025)

On classical advice, sampling advice and complexity assumptions for learning separations
by: Pérez-Guijarro, Jordi
Published: (2024)

Fermionic Independent Set and Laplacian of an independence complex are QMA-hard
by: Rayudu, Chaithanya
Published: (2024)

On the quantum computational complexity of classical linear dynamics with geometrically local interactions: Dequantization and universality
by: Sakamoto, Kazuki, et al.
Published: (2025)

Another generalization of Hadamard test: Optimal sample complexities for learning functions on the unitary group
by: Suruga, Daiki
Published: (2025)

Quantum complexity of the Kronecker coefficients
by: Bravyi, Sergey, et al.
Published: (2023)

On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$
by: Yao, Penghui, et al.
Published: (2023)

Towards a complexity-theoretic dichotomy for TQFT invariants
by: Bridges, Nicolas, et al.
Published: (2025)

Random regular graph states are complex at almost any depth
by: Ghosh, Soumik, et al.
Published: (2024)

Quantum Advantage with Faulty Oracle
by: Lolck, David Rasmussen, et al.
Published: (2024)

Quantum Kolmogorov complexity and quantum correlations in deterministic-control quantum Turing machines
by: Lemus, Mariano, et al.
Published: (2023)

A complexity phase transition at the EPR Hamiltonian
by: Marwaha, Kunal, et al.
Published: (2026)

A Qubit, a Coin, and an Advice String Walk Into a Relational Problem
by: Aaronson, Scott, et al.
Published: (2023)