Copertina

Distributed Quantum Advantage in Locally Checkable Labeling Problems

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Balliu, Alkida, Casagrande, Filippo, d'Amore, Francesco, Equi, Massimo, Keller, Barbara, Lievonen, Henrik, Olivetti, Dennis, Schmid, Gustav, Suomela, Jukka
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Distributed, Parallel, and Cluster Computing Computational Complexity Quantum Physics
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

New Limits on Distributed Quantum Advantage: Dequantizing Linear Programs
di: Balliu, Alkida, et al.
Pubblicazione: (2025)

New Hardness Results for the LOCAL Model via a Simple Self-Reduction
di: Balliu, Alkida, et al.
Pubblicazione: (2025)

Distributed Quantum Advantage for Local Problems
di: Balliu, Alkida, et al.
Pubblicazione: (2024)

Distributed Algorithms for Potential Problems
di: Balliu, Alkida, et al.
Pubblicazione: (2025)

On the Node-Averaged Complexity of Locally Checkable Problems on Trees
di: Balliu, Alkida, et al.
Pubblicazione: (2023)

Is a LOCAL algorithm computable?
di: Cruciani, Antonio, et al.
Pubblicazione: (2026)

The Distributed Complexity Landscape on Trees Depends on the Knowledge About the Network Size
di: Balliu, Alkida, et al.
Pubblicazione: (2026)

No distributed quantum advantage for approximate graph coloring
di: Coiteux-Roy, Xavier, et al.
Pubblicazione: (2023)

Phase transition of the 3-majority opinion dynamics with noisy interactions
di: d'Amore, Francesco, et al.
Pubblicazione: (2021)

Online Locality Meets Distributed Quantum Computing
di: Akbari, Amirreza, et al.
Pubblicazione: (2024)

Phase Transition of a Non-Linear Opinion Dynamics with Noisy Interactions
di: d'Amore, Francesco, et al.
Pubblicazione: (2020)

On the Universality of Round Elimination Fixed Points
di: Balliu, Alkida, et al.
Pubblicazione: (2025)

Completing the Node-Averaged Complexity Landscape of LCLs on Trees
di: Balliu, Alkida, et al.
Pubblicazione: (2024)

Shared Randomness Helps with Local Distributed Problems
di: Balliu, Alkida, et al.
Pubblicazione: (2024)

Distributed Computation with Local Advice
di: Balliu, Alkida, et al.
Pubblicazione: (2024)

On the Limits of Distributed Quantum Computing
di: d'Amore, Francesco
Pubblicazione: (2025)

Classification of Local Optimization Problems in Directed Cycles
di: Boudier, Thomas, et al.
Pubblicazione: (2026)

Solving Sequential Greedy Problems Distributedly with Sub-Logarithmic Energy Cost
di: Balliu, Alkida, et al.
Pubblicazione: (2024)

Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems
di: Hirahara, Shuichi, et al.
Pubblicazione: (2023)

Orientation does not help with 3-coloring a grid in online-LOCAL
di: Boudier, Thomas, et al.
Pubblicazione: (2025)

Pushing Blocks without Fixed Walls via Checkable Gizmos: Push-1 is PSPACE-Complete
di: MIT Hardness Group, et al.
Pubblicazione: (2025)

Pushing Blocks via Checkable Gadgets: PSPACE-completeness of Push-1F and Block/Box Dude
di: Ani, Hayashi, et al.
Pubblicazione: (2024)

Tight Lower Bounds in the Supported LOCAL Model
di: Balliu, Alkida, et al.
Pubblicazione: (2024)

Towards Fully Automatic Distributed Lower Bounds
di: Balliu, Alkida, et al.
Pubblicazione: (2024)

Asynchronous Fault-Tolerant Distributed Proper Coloring of Graphs
di: Balliu, Alkida, et al.
Pubblicazione: (2024)

Neighborhood-Aware Graph Labeling Problem
di: Shahverdikondori, Mohammad, et al.
Pubblicazione: (2026)

Quantum Communication Advantage in TFNP
di: Göös, Mika, et al.
Pubblicazione: (2024)

Formal Framework for Quantum Advantage
di: Buhrman, Harry, et al.
Pubblicazione: (2025)

Local problems in trees across a wide range of distributed models
di: Dhar, Anubhav, et al.
Pubblicazione: (2024)

Constrained Boundary Labeling
di: Depian, Thomas, et al.
Pubblicazione: (2024)

The Computational Advantage of MIP* Vanishes in the Presence of Noise
di: Dong, Yangjing, et al.
Pubblicazione: (2023)

Unconditional Quantum Advantage for Sampling with Shallow Circuits
di: Watts, Adam Bene, et al.
Pubblicazione: (2023)

A Criterion for Post-Selected Quantum Advantage
di: Karamchedu, Chaitanya, et al.
Pubblicazione: (2024)

Strongly Refuting Random CSP without Literals
di: Chan, Siu On, et al.
Pubblicazione: (2026)

On the Advantage of Adaptivity for Sampling with Cell Probes
di: Byramji, Farzan, et al.
Pubblicazione: (2026)

On Computability of Computable Problems
di: Khaliq, Asad
Pubblicazione: (2023)

The Stochastic Arrival Problem
di: Webster, Thomas
Pubblicazione: (2022)

Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals
di: Grier, Daniel, et al.
Pubblicazione: (2025)

Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm
di: Lykov, Danylo, et al.
Pubblicazione: (2022)

The Greedy Coin Change Problem
di: Gupta, Shreya, et al.
Pubblicazione: (2024)