Computational complexity of auditing finite attributes in statistical databases

DOI10.1016/j.jcss.2008.02.002zbMath1140.68016OpenAlexW2152976769MaRDI QIDQ931731

Peter Jonsson, Andrei A. 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)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hypertree decompositions and tractable queries
• Recognizing frozen variables in constraint satisfaction problems
• On the complexity of H-coloring
• Auditing Boolean attributes
• Conjunctive-query containment and constraint satisfaction
• The complexity of solving equations over finite groups
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• The scaling window of the 2-SAT transition
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• A data distortion by probability distribution
• A security machanism for statistical database
• Auditing and Inference Control in Statistical Databases
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Classifying the Complexity of Constraints Using Finite Algebras
• The complexity of satisfiability problems
• The Structure of Tractable Constraint Satisfaction Problems
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• Frozen development in graph coloring

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