ECCC - Reports tagged with NP-hard
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > NP-HARD:
Reports tagged with NP-hard:
TR26-307 | 4th November 2026
Roberto Bruno, Ugo Vaccaro

The Information Bottleneck and the Privacy Funnel are NP-hard

Given a joint distribution $P_{XY}$ of random variables $X,Y$ on finite alphabets, the information
bottleneck method seeks a representation $T$ of $X$ that is as informative as possible about $Y$ while compressing $X$; the privacy funnel asks for a representation that discloses much about $X$ while leaking little about $Y$. ... more >>>




ISSN 1433-8092 | Imprint