Computational complexity of auditing finite attributes in statistical databases

DOI10.1016/J.JCSS.2008.02.002MaRDI QIDQ931731zbMATH OpenOpenAlexFDO

Authors Peter Jonsson, Andrei Krokhin

Publication date 26 June 2008

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2008.02.002

zbMATH Keywords

computational complexitydatabaseconstraint satisfaction problemauditingstatistical query

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Database theory (68P15)

Recommendations

• Auditing Boolean attributes
• scientific article; zbMATH DE number 1953128
• On security of statistical databases
• Theory and Applications of Satisfiability Testing
• scientific article; zbMATH DE number 653236

Cites work

• scientific article; zbMATH DE number 3650557 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1467488 (Why is no real title available?)
• scientific article; zbMATH DE number 1369843 (Why is no real title available?)
• scientific article; zbMATH DE number 839558 (Why is no real title available?)
• A data distortion by probability distribution
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• A security machanism for statistical database
• Auditing Boolean attributes
• Auditing and Inference Control in Statistical Databases
• Classifying the Complexity of Constraints Using Finite Algebras
• Complexity classifications of Boolean constraint satisfaction problems
• Conjunctive-query containment and constraint satisfaction
• Frozen development in graph coloring
• Hypertree decompositions and tractable queries
• On the complexity of H-coloring
• Recognizing frozen variables in constraint satisfaction problems
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The Structure of Tractable Constraint Satisfaction Problems
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• The complexity of constraint satisfaction: an algebraic approach
• The complexity of satisfiability problems
• The complexity of solving equations over finite groups
• The scaling window of the 2-SAT transition

Cited in

(2)

• Statistical database auditing without query denial threat
• Auditing Boolean attributes

This page was built for publication: Computational complexity of auditing finite attributes in statistical databases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q931731)