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

在当今以信息为中心的网络世界中，对保护身份和其他私人信息的担忧日益重要。重要的是，不仅要建立保护这种信息的法律的基线，而且要建立技术基线。 与此同时，数据搜索和分析技术正在出现，能够处理极其大量的信息。因此，需要对数据分析技术进行研究，以提高隐私并以计算效率的方式保护私人信息。 支持数据分析的一个重要技术领域是优化，这是一组使系统尽可能高效的程序。有效地解决优化问题一直是计算机科学的主要主题之一。不幸的是，许多需要在实践中解决的优化问题不太可能有有效的算法解决方案。为了科普这个困难，计算机科学家已经开发了许多实用的近似算法沿着设计这种算法的一般技术。通常，需要解决的优化问题来自对具有潜在隐私限制的真实的数据的分析。 重要的是，有没有已知的通用工具来设计近似算法，这是有效的和可证明private.As一个初步的案例研究，社会网络分析中的社区发现将进行研究。它是私有近似的自然候选者，原因有两个：第一，在许多情况下，底层的社交网络数据可能是敏感的;第二，社区结构不应该严重依赖于网络中的任何单一关系，因此，应该可以找到一个具有良好实用性的私有社区发现算法。该项目的智力价值是在研究所需开发的一般方法，设计有效的差分私人近似算法的组合优化问题。该项目更广泛的影响包括在现实世界的执法和反恐中的应用。

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.