Buchumschlag

No Complete Problem for Constant-Cost Randomized Communication

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Fang, Yuting, Hambardzumyan, Lianna, Harms, Nathaniel, Hatami, Pooya
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Constant-Cost Communication is not Reducible to k-Hamming Distance
von: Fang, Yuting, et al.
Veröffentlicht: (2024)

Structure in Communication Complexity and Constant-Cost Complexity Classes
von: Hatami, Hamed, et al.
Veröffentlicht: (2024)

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

The Log-Rank Conjecture: New Equivalent Formulations
von: Hambardzumyan, Lianna, et al.
Veröffentlicht: (2025)

Factorization norms and an inverse theorem for MaxCut
von: Balla, Igor, et al.
Veröffentlicht: (2025)

Hilbert Functions and Low-Degree Randomness Extractors
von: Golovnev, Alexander, et al.
Veröffentlicht: (2024)

Spiky Rank and Its Applications to Rigidity and Circuits
von: Hambardzumyan, Lianna, et al.
Veröffentlicht: (2026)

Randomized Communication and Implicit Graph Representations
von: Harms, Nathaniel, et al.
Veröffentlicht: (2021)

Better Boosting of Communication Oracles, or Not
von: Harms, Nathaniel, et al.
Veröffentlicht: (2024)

No Constant-Cost Protocol for Point--Line Incidence
von: Göös, Mika, et al.
Veröffentlicht: (2026)

Sign-Rank of $k$-Hamming Distance is Constant
von: Göös, Mika, et al.
Veröffentlicht: (2025)

Pseudodeterministic Communication Complexity
von: Göös, Mika, et al.
Veröffentlicht: (2025)

A Hierarchy for Constant Communication Complexity
von: Ambainis, Andris, et al.
Veröffentlicht: (2025)

Constant Bit-size Transformers Are Turing Complete
von: Li, Qian, et al.
Veröffentlicht: (2025)

On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems
von: DeHaan, Ian, et al.
Veröffentlicht: (2025)

The 2-Attractor Problem is NP-Complete
von: Fuchs, Janosch, et al.
Veröffentlicht: (2023)

Feature Selection and Junta Testing are Statistically Equivalent
von: Beretta, Lorenzo, et al.
Veröffentlicht: (2025)

Random Unitaries in Constant (Quantum) Time
von: Foxman, Ben, et al.
Veröffentlicht: (2025)

Constant-Depth Arithmetic Circuits for Linear Algebra Problems
von: Andrews, Robert, et al.
Veröffentlicht: (2024)

Refuting approaches to the log-rank conjecture for XOR functions
von: Hatami, Hamed, et al.
Veröffentlicht: (2023)

Lower Bounds for Approximate Sign Rank
von: Bindua, Riju, et al.
Veröffentlicht: (2026)

NP-Completeness of Multicast Beamforming in Wireless Communication
von: Shrestha, Sagar
Veröffentlicht: (2025)

Constant-Space, Constant-Randomness Verifiers with Arbitrarily Small Error
von: Gezer, M. Utkan, et al.
Veröffentlicht: (2020)

Towards Solving NP-Complete and Other Hard Problems Efficiently in Practice
von: Digulescu, Mircea-Adrian
Veröffentlicht: (2026)

Searching for Falsified Clause in Random (log n)-CNFs is Hard for Randomized Communication
von: Riazanov, Artur, et al.
Veröffentlicht: (2025)

Limits of Sequential Local Algorithms on the Random $k$-XORSAT Problem
von: Yung, Kingsley
Veröffentlicht: (2024)

Improving the Leading Constant of Matrix Multiplication
von: Alman, Josh, et al.
Veröffentlicht: (2024)

On the Constant-Depth Circuit Complexity of Generating Quasigroups
von: Collins, Nathaniel A., et al.
Veröffentlicht: (2024)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
von: Nederlof, Jesper
Veröffentlicht: (2026)

Wataridori is NP-Complete
von: Ruangwises, Suthee
Veröffentlicht: (2026)

Nondango is NP-Complete
von: Ruangwises, Suthee
Veröffentlicht: (2023)

Constant-depth circuits for polynomial GCD over any characteristic
von: Bhattacharjee, Somnath, et al.
Veröffentlicht: (2025)

Quantum SAT Problems with Finite Sets of Projectors are Complete for a Plethora of Classes
von: Cardoso, Ricardo Rivera, et al.
Veröffentlicht: (2025)

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

NP-Completeness of Neighborhood Balanced Colorings
von: Asaeedi, Saeed
Veröffentlicht: (2024)

Affine Rank Minimization is ER Complete
von: Majumdar, Angshul
Veröffentlicht: (2026)

Communication with Imperfectly Shared Randomness
von: Canonne, Clément L., et al.
Veröffentlicht: (2014)

Gray Codes With Constant Delay and Constant Auxiliary Space
von: Amarilli, Antoine, et al.
Veröffentlicht: (2026)

Constant Degree Direct Product Testers with Small Soundness
von: Bafna, Mitali, et al.
Veröffentlicht: (2024)

The Cheeger Inequality and Coboundary Expansion: Beyond Constant Coefficients
von: First, Uriya A., et al.
Veröffentlicht: (2022)