pipette
ENEnglish

The Information Bottleneck is NP-hard

Roberto Bruno, Ugo Vaccaro

Preprint

En palabras de los autores

Given a joint distribution on a finite alphabet, the information bottleneck method seeks a representation of that is as informative as possible about while compressing , where and are conditionally independent given . We show that computing the optimal value of the information bottleneck problem, as well as its Lagrangian relaxation , is NP-hard. Moreover, unless , neither nor can be approximated in polynomial time within an additive error of order .

Resultado principalEl resumen no menciona limitaciones.

Apareció: viernes, 16 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: Preliminary version