Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Waterloo

$30,000.00

Tractability in structured problems

FY 2011-12

Summary
The idea of structuring information is at the heart of computational problems in diverse application areas such as social sciences, artificial intelligence, biology, Web computing, and many other areas. There may be restrictions in the way that information can be structured, either due to the types of inputs to the problems (the types of information on which the problem is being solved) or due to the type of solution being sought. The goal of my research program is to determine ways of characterizing structure that allows for efficient solutions to fundamental problems; these in turn can be applied to specific problems in target areas. My interests range from extracting structure from problems to developing characterizations and associated solutions, especially for fundamental problems of broad applicability across areas. One type of problem is to reconstruct information given one or more collections of possibly faulty measurements. It is also possible to determine the similarity between two data sets by determining if one appears as a substructure of another, either once or multiple times, exactly or otherwise. These problems can be approached in different ways depending on what similarity measures are used. In some cases, it is also interesting to be able to determine the number of solutions possible. Whereas many problems are stated for one fixed point in time, it may be the case that there are slight changes over time, necessitating modifications to the solution. I am interested in situations in which the new solution is faster to find by using the previous solution than by starting the computation all over again. In particular, I am using as a parameter the amount of drift possible, and looking at problems for which it is difficult, in general, to find solutions that can be computed in time polynomial in the size of the input. I hope to find solutions that are polynomial in the size of the input but possibly a larger function with respect to the parameter; this would yield practical results for situations in which the amount of drift (and hence the parameter) might be small.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
121487-2009
Name nom
Nishimura, Naomi
Department département
Computer Science, David R. Cheriton School of
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2011
Competition year année de concours
2009
Award amount
30000
Program id
RGPIN
Program nane 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
800
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
Information and communication services
Area of application fr
Services d'information et de télécommunications
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
3
Nb partie
5
Application title
Tractability in structured problems
Keyword
NSERC
Application summary
The idea of structuring information is at the heart of computational problems in diverse application areas such as social sciences, artificial intelligence, biology, Web computing, and many other areas. There may be restrictions in the way that information can be structured, either due to the types of inputs to the problems (the types of information on which the problem is being solved) or due to the type of solution being sought. The goal of my research program is to determine ways of characterizing structure that allows for efficient solutions to fundamental problems; these in turn can be applied to specific problems in target areas. My interests range from extracting structure from problems to developing characterizations and associated solutions, especially for fundamental problems of broad applicability across areas. One type of problem is to reconstruct information given one or more collections of possibly faulty measurements. It is also possible to determine the similarity between two data sets by determining if one appears as a substructure of another, either once or multiple times, exactly or otherwise. These problems can be approached in different ways depending on what similarity measures are used. In some cases, it is also interesting to be able to determine the number of solutions possible. Whereas many problems are stated for one fixed point in time, it may be the case that there are slight changes over time, necessitating modifications to the solution. I am interested in situations in which the new solution is faster to find by using the previous solution than by starting the computation all over again. In particular, I am using as a parameter the amount of drift possible, and looking at problems for which it is difficult, in general, to find solutions that can be computed in time polynomial in the size of the input. I hope to find solutions that are polynomial in the size of the input but possibly a larger function with respect to the parameter; this would yield practical results for situations in which the amount of drift (and hence the parameter) might be small.