Computational Discrepancy Theory

计算差异理论

• 批准号: RGPIN-2016-06333
• 负责人: Nikolov, Aleksandar
• 金额: $ 2.62万
• 依托单位: University of Toronto
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=710254
• 关键词: Computational; Discrepancy; Theory

The focus of this research is computational aspects of combinatorial discrepancy theory, including the development of applications of discrepancy to computer science, and understanding the computational complexity of discrepancy itself. First, we propose to study applications of discrepancy theory to differential privacy. Differential privacy is a recent approach to achieving strong provable privacy guarantees in the analysis of sensitive data. The accuracy of query answers computed under differential privacy must necessarily be traded off for the privacy guarantees in any non-trivial analysis. We propose to generalize the connection between discrepancy theory and differential privacy we developed in prior work in the context of linear queries, in order to characterize the necessary and sufficient error for privately answering convex minimization queries. These queries encompass a large number of primitives used in machine learning and statistics. We further propose to study applications of discrepancy theory to the design of efficient approximation algorithms for hard optimization problems. Combinatorial discrepancy has the potential to generalize and unify classical rounding methods for linear and semidefinite programs, such as randomized and iterative rounding, and was recently used to give an improved approximation algorithm for the bin packing problem. We propose to study the applicability of discrepancy-based rounding to other fundamental optimization problems. Moreover, recent progress on spectral notions of discrepancy, particularly the resolution of the Kadison-Singer problem, suggests that discrepancy based rounding may be applicable to semidefinite programs as well. Conversely, discrepancy lower bounds imply negative results for natural classes of rounding algorithms. We propose to study whether the negative results proved via discrepancy methods can be turned into proofs of integrality gaps, i.e. gaps between the optimal integral solution and the value of a linear programming relaxation. Finally, we propose to study computational questions in discrepancy theory itself. The computational complexity of many of the important measures of discrepancy remains open. Moreover, some of the most powerful methods of constructing low discrepancy structures are only existential, and do not provide efficient algorithms. Both of these concerns currently limit the applicability of discrepancy methods to algorithm design. We propose to extend tools we have developed in prior work to understand the complexity of approximating hereditary discrepancy to other combinatorial discrepancy measures. We also propose to develop algorithmic techniques to construct low discrepancy objects.

本研究的重点是计算方面的组合差异理论，包括差异的应用程序，计算机科学的发展，并了解计算复杂性的差异本身。 首先，我们建议研究差异理论在差异隐私中的应用。差分隐私是最近的一种方法，以实现强有力的可证明的隐私保证在敏感数据的分析。在任何非平凡的分析中，在差分隐私下计算的查询答案的准确性必须与隐私保证相权衡。我们建议推广的差异理论和差分隐私之间的联系，我们在以前的工作中开发的线性查询的背景下，为了刻画的必要和充分的错误，私下回答凸最小化查询。这些查询包含了机器学习和统计中使用的大量原语。 我们进一步建议研究应用差异理论设计有效的近似算法硬优化问题。组合差异有可能推广和统一经典的舍入方法的线性和半定规划，如随机和迭代舍入，最近被用来给一个改进的近似算法装箱问题。我们建议研究基于差异的舍入对其他基本优化问题的适用性。此外，最近的进展谱概念的差异，特别是解决的Kadison-Singer问题，表明差异为基础的四舍五入可能适用于半定程序。相反，差异下限意味着舍入算法的自然类的负面结果。我们建议研究通过差异方法证明的否定结果是否可以变成完整性差距的证明，即最佳积分解和线性规划松弛值之间的差距。 最后，我们建议研究计算问题的差异理论本身。许多重要的差异度量的计算复杂性仍然是开放的。此外，一些构造低差异结构的最强大的方法仅仅是存在的，并且不提供有效的算法。这两个问题目前限制了差异方法的算法设计的适用性。我们建议扩展工具，我们已经开发了在以前的工作，以了解近似遗传差异的复杂性，其他组合的差异措施。我们还建议开发算法技术来构建低差异对象。