III: RI: Small: Efficient Privacy Methods Using Linear Programming

点击翻译按钮获取中文摘要

In today's information-centric networked world, concerns about protecting identities and other private information are growing in importance. It is important to establish not only a legal baseline but also a technological baseline that protects such information. At the same time, data search and analysis technologies are emerging that are capable of processing extremely large volumes of information. As a result, research is needed into data analysis technologies that enhance privacy and protect private information in a computationally efficient manner. One important area of technology that supports data analysis is optimization, a set of procedures that make a system as efficient as possible. Solving optimization problems efficiently has been one of the major themes of computer science throughout the history of the field. Unfortunately many optimization problems that need to be solved in practice are unlikely to have efficient algorithmic solutions. To cope with this difficulty, computer scientists have developed numerous practical approximation algorithms along with general techniques for designing such algorithms. Often the optimization problems that need to be solved arise from the analysis of real data with potential privacy restrictions. Importantly, there are no known general tools to design approximation algorithms which are both efficient and provably private.As an initial case study, community discovery in social network analysis will be studied. It is a natural candidate for private approximation for two reasons: first, the underlying social network data in many cases can be sensitive; second, community structure should not depend crucially on any single relation in the network, and, therefore, it should be possible to find a private community discovery algorithm with good utility. The intellectual merit of the project is in the research required to develop general methods for designing efficient differentially private approximation algorithms for combinatorial optimization problems. The project's broader impacts include applications in real-world law enforcement and counterterrorism.