This paper explores the complexity of the privacy problem. In particular the computational complexity properties of the privacy problem are examined. Prior work in this area explored the recursion theoretic properties and viewed the privacy problem as a form of the inference problem. This work showed that the privacy problem in general was unsolvable. The PIs follow up on this prior work and propose to explore the more important aspects of the privacy problem and that is the complexity of the privacy problem. They also view the privacy problem as a form of inference problem in databases and subsequently propose to develop a complexity theory for privacy problem based on deductive databases and then prove some properties of the problem.
Privacy is becoming a very important research area and we are funding a number of efforts on privacy. It is critical that the complexity aspects of the privacy problem be examined. The PIs are top researchers in complexity theory and databases. They are highly qualified to do this research. They have published in top journals such as the Journal of the ACM and Journal of Computer and Systems Sciences. This research could produce some breakthrough results.
