Total Protection of Analytic Invariant Information in Cross Tabulated Tables
<|reference_start|>Total Protection of Analytic Invariant Information in Cross Tabulated Tables: To protect sensitive information in a cross tabulated table, it is a common practice to suppress some of the cells in the table. An analytic invariant is a power series in terms of the suppressed cells that has a unique feasible value and a convergence radius equal to +\infty. Intuitively, the information contained in an invariant is not protected even though the values of the suppressed cells are not disclosed. This paper gives an optimal linear-time algorithm for testing whether there exist nontrivial analytic invariants in terms of the suppressed cells in a given set of suppressed cells. This paper also presents NP-completeness results and an almost linear-time algorithm for the problem of suppressing the minimum number of cells in addition to the sensitive ones so that the resulting table does not leak analytic invariant information about a given set of suppressed cells.<|reference_end|>
@article{kao2001total,
    title={Total Protection of Analytic Invariant Information in Cross Tabulated
  Tables},
    author={Ming-Yang Kao},
    journal={SIAM Journal on Computing, 26(1):231--242, February 1997},
    year={2001},
    archivePrefix={arXiv},
    eprint={cs/0101032},
    primaryClass={cs.CR cs.DM cs.DS}
}