Cover Image

Communication Complexity is NP-hard

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Hirahara, Shuichi, Ilango, Rahul, Loff, Bruno
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration
by: Hirahara, Shuichi, et al.
Published: (2024)

Optimal Coding for Randomized Kolmogorov Complexity and Its Applications
by: Hirahara, Shuichi, et al.
Published: (2024)

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

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

Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration
by: Hirahara, Shuichi, et al.
Published: (2025)

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

Asymptotically Optimal Inapproximability of Maxmin $k$-Cut Reconfiguration
by: Hirahara, Shuichi, et al.
Published: (2024)

NP-hardness of SVP in Euclidean Space
by: Wan, Daqing
Published: (2026)

Optimizing for aggressive-style strategies in Flesh and Blood is NP-hard
by: Romão, Leonardo Gasparini, et al.
Published: (2025)

Reachability of Independent Sets and Vertex Covers Under Extended Reconfiguration Rules
by: Hirahara, Shuichi, et al.
Published: (2025)

King Chasing Problem in Chinese Chess is NP-hard
by: Li, Chao, et al.
Published: (2026)

NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials
by: Baraskar, Omkar, et al.
Published: (2024)

Quantum Max-Cut is NP hard to approximate
by: Piddock, Stephen
Published: (2025)

Computing the EHZ capacity is NP-hard
by: Leipold, Karla, et al.
Published: (2024)

Prove Symbolic Regression is NP-hard by Symbol Graph
by: Song, Jinglu, et al.
Published: (2024)

Data Debugging is NP-hard for Classifiers Trained with SGD
by: Guo, Zizheng, et al.
Published: (2024)

Freeze-Tag is NP-hard in 2D with $L_1$ distance
by: Silva, Lucas de Oliveira, et al.
Published: (2025)

Approximating 1-in-3 SAT by linearly ordered hypergraph 3-colouring is NP-hard
by: Krokhin, Andrei, et al.
Published: (2025)

Two NP-hard Extensions of the Spearman Footrule even for a Small Constant Number of Voters
by: Durand, Martin
Published: (2026)

NP-Completeness of Multicast Beamforming in Wireless Communication
by: Shrestha, Sagar
Published: (2025)

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

Computational-Statistical Tradeoffs from NP-hardness
by: Blanc, Guy, et al.
Published: (2025)

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

Scheme-theoretic Approach to Computational Complexity I. The Separation of P and NP
by: Çivril, Ali
Published: (2021)

The color code, the surface code, and the transversal CNOT: NP-hardness of minimum-weight decoding
by: Gu, Shouzhen, et al.
Published: (2026)

P=NP
by: Deng, Zikang
Published: (2024)

Wataridori is NP-Complete
by: Ruangwises, Suthee
Published: (2026)

P vs. NP
by: Uribe, Daniel
Published: (2016)

On P Versus NP
by: Gordeev, Lev
Published: (2020)

Nondango is NP-Complete
by: Ruangwises, Suthee
Published: (2023)

On $NP \cap coNP$ proof complexity generators
by: Krajicek, Jan
Published: (2025)

Proofs of NP = coNP = PSPACE: Current upgrade
by: Gordeev, Lev, et al.
Published: (2023)

A Critique of Lin's "On $\text{NP}$ versus $\text{coNP}$ and Frege Systems"
by: DeJesse, Nicholas, et al.
Published: (2025)

BusOut is NP-complete
by: Ishibashi, Takehiro, et al.
Published: (2025)

On Kernelization with Access to NP-Oracles
by: Molter, Hendrik, et al.
Published: (2025)

Complexity and hardness of random peaked circuits
by: Zhang, Yuxuan
Published: (2025)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
by: Nederlof, Jesper
Published: (2026)

A Critique of Deng's "P=NP"
by: Humphreys, Isabel, et al.
Published: (2025)

NP-Completeness of Neighborhood Balanced Colorings
by: Asaeedi, Saeed
Published: (2024)