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.