research
The Information Bottleneck Is NP-Hard
Even approximating the optimum within a shrinking additive error remains hard unless P equals NP.
Summary
Even approximating the optimum within a shrinking additive error remains hard unless P equals NP.
The information bottleneck seeks a compressed representation of one variable that preserves information about another. This paper proves that computing both the constrained optimum and its Lagrangian relaxation is NP-hard. Unless P equals NP, neither can be approximated in polynomial time within additive error on the order of the input alphabet size to the negative three-halves. The result concerns worst-case computation, not every practical heuristic.
Why it matters
Even approximating the optimum within a shrinking additive error remains hard unless P equals NP.
Limits and context
- The result concerns worst-case computation, not every practical heuristic.
Key claims
Even approximating the optimum within a shrinking additive error remains hard unless P equals NP.
Qualification: The result concerns worst-case computation, not every practical heuristic.
Evidence: source-2026-10-18-017
Sources
- arXiv preprint 2610.22272, original v1arXiv · primary research
Corrections
No corrections have been recorded for this story.