Algorithmic problems emerging in new networking technologies

点击翻译按钮获取中文摘要

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.