@inproceedings{c4b5e68011a74dff89110112cfa2c5d9,
title = "Total protection of analytic invariant information in cross tabulated tables",
abstract = "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 +∞. 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 lineartime 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.",
author = "Kao, {Ming Yang}",
note = "Funding Information: This paper investigatetsh e complexityo f how to protect a broad class of informationc ontainedin a two-dimensionatal blethat publishes( 1) the values of all cells excepta set of sensitiveo nes,which are suppressed, and (2) an upper bound and a lower bound for each cell, and (3) all row sums and column sums *Departmenotf ComputeSr cience,D ukeU niversity,D urham,N C 27706. Supporteidn part by NSF grantsM CS-8116678D, CR-8405478a, ndC CR-9101385P. art of this work was donew hile the authorsw erea t the Departmenotf ComputeSr cienceY, ale University,N ew Haven,C onnecticu0t6 520. Funding Information: Supported in part by NSFNational Science Foundation grants MCS-8116678, DCR-8405478, and CCR-9101385. Part of this work was done while the authors were at the Department of Computer Science, Yale University, New Haven, Connecticut 06520. Publisher Copyright: {\textcopyright} 1994, Springer Verlag. All rights reserved.; Proceedings of the 11th Symposium on Theoretical Aspects of Computer Science (STACS'94) ; Conference date: 24-02-1994 Through 26-02-1994",
year = "1994",
doi = "10.1007/3-540-57785-8_185",
language = "English (US)",
isbn = "9783540577850",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "723--734",
editor = "Patrice Enjalbert and Mayr, {Ernst W.} and Wagner, {Klaus W.}",
booktitle = "STACS 1994 - 11th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings",
}