Copertina

A Hierarchy for Constant Communication Complexity

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Ambainis, Andris, Klauck, Hartmut, Lim, Debbie
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

A sharp interaction-degree threshold for simulating QAOA
di: Āboliņš, Ralfs, et al.
Pubblicazione: (2026)

Quantum Algorithm for Apprenticeship Learning
di: Ambainis, Andris, et al.
Pubblicazione: (2025)

Quantum Advantages in (n,d)->1 Random Access Codes
di: Ambainis, Andris, et al.
Pubblicazione: (2015)

Structure in Communication Complexity and Constant-Cost Complexity Classes
di: Hatami, Hamed, et al.
Pubblicazione: (2024)

Oblivious Complexity Classes Revisited: Lower Bounds and Hierarchies
di: Gajulapalli, Karthik, et al.
Pubblicazione: (2025)

A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model
di: Ambainis, Andris, et al.
Pubblicazione: (2025)

No Complete Problem for Constant-Cost Randomized Communication
di: Fang, Yuting, et al.
Pubblicazione: (2024)

Equality is Far Weaker than Constant-Cost Communication
di: Göös, Mika, et al.
Pubblicazione: (2025)

Constant-Cost Communication is not Reducible to k-Hamming Distance
di: Fang, Yuting, et al.
Pubblicazione: (2024)

On the Pure Quantum Polynomial Hierarchy and Quantified Hamiltonian Complexity
di: Grewal, Sabee, et al.
Pubblicazione: (2025)

Pseudodeterministic Communication Complexity
di: Göös, Mika, et al.
Pubblicazione: (2025)

From Probability to Counterfactuals: the Increasing Complexity of Satisfiability in Pearl's Causal Hierarchy
di: Dörfler, Julian, et al.
Pubblicazione: (2024)

A Hierarchy of Tinhofer Graphs: Separations and Membership Testing
di: Bhattacharjee, Sutanay, et al.
Pubblicazione: (2026)

Communication Complexity is NP-hard
di: Hirahara, Shuichi, et al.
Pubblicazione: (2025)

Hierarchies within TFNP: building blocks and collapses
di: Ghentiyala, Surendra, et al.
Pubblicazione: (2025)

Width Hierarchy for k-OBDD of Small Width
di: Khadiev, Kamil
Pubblicazione: (2015)

An XOR Lemma for Deterministic Communication Complexity
di: Iyer, Siddharth, et al.
Pubblicazione: (2024)

Multiparty Communication Complexity of Collision Finding
di: Beame, Paul, et al.
Pubblicazione: (2024)

Optimal Communication Complexity of Chained Index
di: Sundaresan, Janani
Pubblicazione: (2024)

Hilbert's Nullstellensatz is in the Counting Hierarchy
di: Andrews, Robert, et al.
Pubblicazione: (2026)

Complexity Aspects of the Extension of Wagner's Hierarchy to $k$-Partitions
di: Podolskii, Vladimir, et al.
Pubblicazione: (2024)

A Quantum Pigeonhole Principle and Two Semidefinite Relaxations of Communication Complexity
di: Dvořák, Pavel, et al.
Pubblicazione: (2024)

Improving the Leading Constant of Matrix Multiplication
di: Alman, Josh, et al.
Pubblicazione: (2024)

On a Hierarchy of Spectral Invariants for Graphs
di: Arvind, V., et al.
Pubblicazione: (2023)

One-Way Communication Complexity of Partial XOR Functions
di: Podolskii, Vladimir V., et al.
Pubblicazione: (2023)

A SUBSET-SUM Characterisation of the A-Hierarchy
di: Gutleben, Jan, et al.
Pubblicazione: (2024)

A Lower Bound on the Constant in the Fourier Min-Entropy/Influence Conjecture
di: Biswas, Aniruddha, et al.
Pubblicazione: (2022)

Constant Time with Minimal Preprocessing, a Robust and Extensive Complexity Class
di: Grandjean, Étienne, et al.
Pubblicazione: (2025)

On the Hierarchies for Deterministic, Nondeterministic and Probabilistic Ordered Read-k-times Branching Programs
di: Khadiev, Kamil
Pubblicazione: (2016)

One-way Communication Complexity of Minimum Vertex Cover in General Graphs
di: Derakhshan, Mahsa, et al.
Pubblicazione: (2025)

Refuting the Direct Sum Conjecture for Total Functions in Deterministic Communication Complexity
di: Mackenzie, Simon, et al.
Pubblicazione: (2024)

Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity
di: de Rezende, Susanna F., et al.
Pubblicazione: (2026)

Communication Complexity of Disjointness under Product Distributions
di: Hunter, Zach, et al.
Pubblicazione: (2026)

Gaps, Ambiguity, and Establishing Complexity-Class Containments via Iterative Constant-Setting
di: Hemaspaandra, Lane A., et al.
Pubblicazione: (2021)

Constant-depth circuits for polynomial GCD over any characteristic
di: Bhattacharjee, Somnath, et al.
Pubblicazione: (2025)

The Entangled Quantum Polynomial Hierarchy Collapses
di: Grewal, Sabee, et al.
Pubblicazione: (2024)

New Algebrization Barriers to Circuit Lower Bounds via Communication Complexity of Missing-String
di: Chen, Lijie, et al.
Pubblicazione: (2025)

On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy
di: Grüne, Christoph, et al.
Pubblicazione: (2024)

Gateways to Tractability for Satisfiability in Pearl's Causal Hierarchy
di: Ganian, Robert, et al.
Pubblicazione: (2025)

Oracle Separations for the Quantum-Classical Polynomial Hierarchy
di: Agarwal, Avantika, et al.
Pubblicazione: (2024)