Grant: Discovery Grants Program - Individual
University of British Columbia
$19,000.00
Algorithms and complexity of hard problems: bridging the gap between theory and practice
FY 2013-14
Summary
It is a widely-held belief among many researchers in algorithmics and artificial intelligence that there remains a lack of theory on the nature of various computationally-hard algorithmic problems in practical fields. The worst-case oriented theory of computational complexity, while having had an enormous impact to the computing world, has proven to be unsatisfactory for providing the much-needed insight into the behavior of many practical algorithms when applied to ""typical"" instances of real-world problems. In recent years, several new paradigms have emerged to help improve our ability to cope with the intractability of hard algorithmic problems. Among them are probabilistic analysis such as the study of phase transitions and the smoothed analysis of specific algorithms, the theory of parameterized complexity and algorithms, and the theory of exact (exponential-time) algorithms.I am particularly interested in the probabilistic analysis of intractable problems, the study of algorithmic aspects of random discrete structures, and the design of algorithms and heuristics. The insights learned from these studies have enormous application to problems in practical domains such as bioinformatics and networking. The proposed research program has two closely-related foci: (1) the probabilistic analysis of random instances of intractable problems; and (2) the design of theory-motivated heuristics and speedup techniques for search-tree-based algorithms and the development of practical industrial-strength software solvers for hard problems.Progress made by the success of this research program will help bridge the gap between the theoretical development of algorithmics and the practice of designing efficient algorithmic solutions to real-world problems.
Program
Discovery Grants Program - Individual
Recipient
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
327587-2009
Name nom
Gao, Yong
Department département
Okanagan - Computer Science, Mathematics, Physics and Statistics
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
2013
Competition year année de concours
2009
Award amount
19000
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
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
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
2800
Research subject group en
Artificial intelligence
Research subject group fr
Intelligence artificielle
Research subject en
Artificial intelligence (computer vision, use2603)
Research subject fr
Intelligence artificielle (vision artificielle, utiliser 2603)
Partie
5
Nb partie
5
Application title
Algorithms and complexity of hard problems: bridging the gap between theory and practice
Keyword
NSERC
Application summary
It is a widely-held belief among many researchers in algorithmics and artificial intelligence that there remains a lack of theory on the nature of various computationally-hard algorithmic problems in practical fields. The worst-case oriented theory of computational complexity, while having had an enormous impact to the computing world, has proven to be unsatisfactory for providing the much-needed insight into the behavior of many practical algorithms when applied to ""typical"" instances of real-world problems. In recent years, several new paradigms have emerged to help improve our ability to cope with the intractability of hard algorithmic problems. Among them are probabilistic analysis such as the study of phase transitions and the smoothed analysis of specific algorithms, the theory of parameterized complexity and algorithms, and the theory of exact (exponential-time) algorithms.I am particularly interested in the probabilistic analysis of intractable problems, the study of algorithmic aspects of random discrete structures, and the design of algorithms and heuristics. The insights learned from these studies have enormous application to problems in practical domains such as bioinformatics and networking. The proposed research program has two closely-related foci: (1) the probabilistic analysis of random instances of intractable problems; and (2) the design of theory-motivated heuristics and speedup techniques for search-tree-based algorithms and the development of practical industrial-strength software solvers for hard problems.Progress made by the success of this research program will help bridge the gap between the theoretical development of algorithmics and the practice of designing efficient algorithmic solutions to real-world problems.