Grant: Discovery Grants Program - Individual
University of British Columbia
$38,000.00
Algorithms: Sparsification and Applications
EF 2016-17
Résumé
Modern algorithmic research has two compelling justifications. First, the field aims to study foundational questions with significant technical depth, frequently leading to results of high scientific merit. Second, the field has developed many powerful algorithmic tools that can have great impact in applications. My passion for algorithmic research stems from a desire to contribute results and train students in both of these directions.
With my MSc students at UBC, I aim to find applied areas with problems that can be attacked by modern algorithmic tools. Together we have found novel applications of discrepancy algorithms to machine learning problems, of streaming algorithms to caching problems, and of graph embedding algorithms to information visualization problems. All of this work is being published in significant computer science conferences. One of the projects was conducted together with a local startup company; that work has been patented and incorporated into their product. Technology transfer from theory to applications remains a goal for my future MSc projects.
The second thrust of my research is on foundational questions in algorithms. This work focuses on a phenomenon known as sparsification: removing parts of an object to make it simpler, while approximately preserving its overall structure. Sparsification of graphs has seen dramatic progress in the past 10 years. One remarkable result shows that, in any graph, one can find a linear number of edges that preserve its cuts and its spectral structure. With my Waterloo students we have published new sparsification results in a top-tier conference and journal.
In combinatorics, sparsification is known as discrepancy theory. Over the past five years there has been a revolution in discrepancy. Several problems that lacked an algorithmic solution for decades now finally have one. This work has already led to the solution of the Kadison-Singer problem, a notorious problem in pure mathematics. A major open question is to find an algorithmic version of that result. Together with my students and external collaborators, my recent and future research aims to push the boundary of discrepancy theory.
Achieving the goals of this proposal will lead to theoretical algorithms of substantial scientific value, and practical algorithms with impact on other fields. My intention is to pursue the foundational questions with UBC students, and the applied questions together with local industry partners.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
British Columbia, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2016-04359
Name nom
Harvey, Nicholas
Department département
Computer Science - Computer Science
Organization id
2
Institution établissement
University of British Columbia
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2016
Competition year année de concours
2016
Award amount
38000
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
Algorithms: Sparsification and Applications
Keyword
NSERC
Application summary
Modern algorithmic research has two compelling justifications. First, the field aims to study foundational questions with significant technical depth, frequently leading to results of high scientific merit. Second, the field has developed many powerful algorithmic tools that can have great impact in applications. My passion for algorithmic research stems from a desire to contribute results and train students in both of these directions.
With my MSc students at UBC, I aim to find applied areas with problems that can be attacked by modern algorithmic tools. Together we have found novel applications of discrepancy algorithms to machine learning problems, of streaming algorithms to caching problems, and of graph embedding algorithms to information visualization problems. All of this work is being published in significant computer science conferences. One of the projects was conducted together with a local startup company; that work has been patented and incorporated into their product. Technology transfer from theory to applications remains a goal for my future MSc projects.
The second thrust of my research is on foundational questions in algorithms. This work focuses on a phenomenon known as sparsification: removing parts of an object to make it simpler, while approximately preserving its overall structure. Sparsification of graphs has seen dramatic progress in the past 10 years. One remarkable result shows that, in any graph, one can find a linear number of edges that preserve its cuts and its spectral structure. With my Waterloo students we have published new sparsification results in a top-tier conference and journal.
In combinatorics, sparsification is known as discrepancy theory. Over the past five years there has been a revolution in discrepancy. Several problems that lacked an algorithmic solution for decades now finally have one. This work has already led to the solution of the Kadison-Singer problem, a notorious problem in pure mathematics. A major open question is to find an algorithmic version of that result. Together with my students and external collaborators, my recent and future research aims to push the boundary of discrepancy theory.
Achieving the goals of this proposal will lead to theoretical algorithms of substantial scientific value, and practical algorithms with impact on other fields. My intention is to pursue the foundational questions with UBC students, and the applied questions together with local industry partners.