Computational Discrepancy Theory

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

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.