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.