Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Toronto

$36,000.00

Computational Discrepancy Theory

EF 2016-17

Résumé
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.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2016-06333
Name nom
Nikolov, Aleksandar
Department département
Computer Science (St. George Campus) - Computer Science (St. George Campus)
Organization id
31
Institution établissement
University of Toronto
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2016
Competition year année de concours
2016
Award amount
36000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
801
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer software
Area of application fr
Logiciel
Research subject code
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Partie
1
Nb partie
5
Application title
Computational Discrepancy Theory
Keyword
NSERC
Application summary
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.