NP-Completeness and ETH-Based Additive Inapproximability of Deterministic Communication Complexity via Relaxed Interlacing
cs.CC, cs.DS, math.CO
Submitted: 2025-08-07
Updated: 2026-10-22
Terminology
Related papers
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- Optimal Unambiguous DNFs and Alon-Saks-Seymour
- On the Limits of Quantum Multiparty Simultaneous Communication
- Learning, Compression, and Meta-Complexity
- Hardware-Algorithm Co-Optimization of Early-Exit Neural Networks for Multi-Core Edge Accelerators
- Quantum Fine-Grained Lower Bounds for SetDisjointness via Sub-Linear Reductions from 3SUM