The $k$-anonymity Problem is Hard

Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi

The problem of publishing personal data without giving up privacy is becoming increasingly important. An interesting formalization recently proposed is the k-anonymity. This approa…