Grant: Discovery Grants Program - Individual
Simon Fraser University
$56,000.00
Algorithmic problems emerging in new networking technologies
EF 2022-23
Résumé
Over the past few years, my research interests centered around three main areas: theoretical aspects and algorithms for communication in interconnection networks, computational biology, and graph theory. In the future I expect to continue to be active in all three areas, however I will focus on problems related to the first area as problems emerging from fascinating new technologies often utilize methods from combinatorics, graph theory, computational geometry, design theory, and algebraic combinatorics that are main tools in my research.In particular, I want to focus, but not restrict, on ad-hoc, sensor, and social networks. My goal is to build on my expertise, develop techniques, and answer some of the emerging questions. I briefly describe some of them in what follows.1) Modern networks of all kinds may have millions of nodes and connections and, in fact, many of them may not be even present at a time. It is impossible to utilize classical algorithms to solve problems on such networks. In past years, local algorithms that utilize a robot moving on the network and at each step the robot can use only a local portion of the network have been proposed for several fundamental problems. Traversal, or s,t-connectivity, is one of such fundamental problems and has been extensively studied for many years. In a seminal work, Omer Reingold showed that there is a local algorithm that solves s,t-connectivity in log n space provided we know n the number of nodes in the network. If we allow for extra information, for example geometric (nodes of network will have coordinates available to the robot geometric graphs), then much stronger local traversal can be guaranteed. I propose to continue my research in this direction.2) Some of the techniques for local traversal on geometric graphs that I have developed required the geometric graph to satisfy certain structural condition. I propose to relax this conditions by over-imposing a "virtual" network that will consist of virtual nodes and connections, and will be build by the robot in its memory and will guarantee that the structural condition in the "union" of the two networks is satisfied. The virtual network will be regular, for example a grid, so that it can be computed and amalgamated with the existing local part of the network. This is a new approach that I believe will be very useful in approaching many network problems in local way. 3) The maze traversal algorithms have been extensively studied in literature. With current technology advent and initiatives moving towards mapping and navigating interior, such algorithms are gaining more and more popularity. I propose to study problems of maze traversal with very simple and limited robots when the maze is unknown or when the position of robot in the maze is unknown.
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-2018-03900
Name nom
Stacho, Ladislav
Department département
Mathematics - Mathematics
Organization id
5
Institution établissement
Simon Fraser University
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2022
Competition year année de concours
2018
Award amount
56000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
803
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 communications
Area of application fr
Téléinformatique
Research subject code
2700
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Information technology
Research subject fr
Technologie de l'information
Installment
inst:5;6
Partie
2
Nb partie
6
Application title
Algorithmic problems emerging in new networking technologies
Application summary
Over the past few years, my research interests centered around three main areas: theoretical aspects and algorithms for communication in interconnection networks, computational biology, and graph theory. In the future I expect to continue to be active in all three areas, however I will focus on problems related to the first area as problems emerging from fascinating new technologies often utilize methods from combinatorics, graph theory, computational geometry, design theory, and algebraic combinatorics that are main tools in my research.In particular, I want to focus, but not restrict, on ad-hoc, sensor, and social networks. My goal is to build on my expertise, develop techniques, and answer some of the emerging questions. I briefly describe some of them in what follows.1) Modern networks of all kinds may have millions of nodes and connections and, in fact, many of them may not be even present at a time. It is impossible to utilize classical algorithms to solve problems on such networks. In past years, local algorithms that utilize a robot moving on the network and at each step the robot can use only a local portion of the network have been proposed for several fundamental problems. Traversal, or s,t-connectivity, is one of such fundamental problems and has been extensively studied for many years. In a seminal work, Omer Reingold showed that there is a local algorithm that solves s,t-connectivity in log n space provided we know n the number of nodes in the network. If we allow for extra information, for example geometric (nodes of network will have coordinates available to the robot geometric graphs), then much stronger local traversal can be guaranteed. I propose to continue my research in this direction.2) Some of the techniques for local traversal on geometric graphs that I have developed required the geometric graph to satisfy certain structural condition. I propose to relax this conditions by over-imposing a "virtual" network that will consist of virtual nodes and connections, and will be build by the robot in its memory and will guarantee that the structural condition in the "union" of the two networks is satisfied. The virtual network will be regular, for example a grid, so that it can be computed and amalgamated with the existing local part of the network. This is a new approach that I believe will be very useful in approaching many network problems in local way. 3) The maze traversal algorithms have been extensively studied in literature. With current technology advent and initiatives moving towards mapping and navigating interior, such algorithms are gaining more and more popularity. I propose to study problems of maze traversal with very simple and limited robots when the maze is unknown or when the position of robot in the maze is unknown.