Imagen de Portada

A Quantum Pigeonhole Principle and Two Semidefinite Relaxations of Communication Complexity

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Dvořák, Pavel, Loff, Bruno, Sherif, Suhail
Formato:	Preprint
Publicado:	2024
Materias:	Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

On Pigeonhole Principles and Ramsey in TFNP
por: Jain, Siddhartha, et al.
Publicado: (2024)

Key-agreement exists if and only if the "interactive vs non interactive Kolmogorov problem" is not in ioBPP: a short proof
por: Bauwens, Bruno, et al.
Publicado: (2025)

Lower Bounds for Bit Pigeonhole Principles in Bounded-Depth Resolution over Parities
por: Byramji, Farzan, et al.
Publicado: (2025)

Smoothed analysis of deterministic discounted and mean-payoff games
por: Loff, Bruno, et al.
Publicado: (2024)

Exponential Separation Between Powers of Regular and General Resolution Over Parities
por: Bhattacharya, Sreejata Kishor, et al.
Publicado: (2024)

On the Complexity of Target Set Selection in Simple Geometric Networks
por: Dvořák, Michal, et al.
Publicado: (2023)

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
por: Assadi, Sepehr, et al.
Publicado: (2024)

Boolean Circuit Complexity and Two-Dimensional Cover Problems
por: Cavalar, Bruno P., et al.
Publicado: (2025)

NP-Completeness of Deterministic Communication Complexity via Relaxed Interlacing
por: Gaspers, Serge, et al.
Publicado: (2025)

Generalized minimum 0-extension problem and discrete convexity
por: Dvorak, Martin, et al.
Publicado: (2021)

A Hierarchy for Constant Communication Complexity
por: Ambainis, Andris, et al.
Publicado: (2025)

Pseudodeterministic Communication Complexity
por: Göös, Mika, et al.
Publicado: (2025)

A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity
por: Wu, Xudong, et al.
Publicado: (2025)

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

Quantum and Classical Communication Complexity of Permutation-Invariant Functions
por: Guan, Ziyi, et al.
Publicado: (2023)

List Locally Surjective Homomorphisms in Hereditary Graph Classes
por: Dvořák, Pavel, et al.
Publicado: (2022)

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

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

Optimal Communication Complexity of Chained Index
por: Sundaresan, Janani
Publicado: (2024)

Maximum Separation of Quantum Communication Complexity With and Without Shared Entanglement
por: Hasegawa, Atsuya, et al.
Publicado: (2025)

A Meta-Complexity Characterization of Quantum Cryptography
por: Cavalar, Bruno P., et al.
Publicado: (2024)

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

Quantum Complexity vs Classical Complexity: A Survey
por: Vaezi, Arash, et al.
Publicado: (2023)

Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems
por: Lichter, Moritz, et al.
Publicado: (2024)

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

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

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

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

Monotone Circuit Complexity of Matching
por: Cavalar, Bruno, et al.
Publicado: (2025)

Black-Box PWPP Is Not Turing-Closed
por: Hubáček, Pavel
Publicado: (2026)

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

Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes
por: Grigorescu, Elena, et al.
Publicado: (2025)

On the Nature and Complexity of an Impartial Two-Player Variant of the Game Lights-Out
por: Fiorini, Eugene, et al.
Publicado: (2024)

The Communication Complexity of Approximating Matrix Rank
por: Sherstov, Alexander A., et al.
Publicado: (2024)

A Brief Introduction to Quantum Query Complexity
por: Hamoudi, Yassine
Publicado: (2025)

Bosonic Quantum Computational Complexity
por: Chabaud, Ulysse, et al.
Publicado: (2024)

On the Complexity of Decoded Quantum Interferometry
por: Marwaha, Kunal, et al.
Publicado: (2025)

Complexity of the Guarded Two-Variable Fragment with Counting Quantifiers
por: Pratt-Hartmann, Ian
Publicado: (2006)

Complexity Theory for Quantum Promise Problems
por: Chia, Nai-Hui, et al.
Publicado: (2024)