Algorithmic problems emerging in new networking technologies

在过去的几年里，我的研究兴趣集中在三个主要领域：互连网络中通信的理论方面和算法，计算生物学和图论。在未来，我希望继续活跃于这三个领域，但我将专注于与第一个领域相关的问题，因为从迷人的新技术中出现的问题通常使用组合学、图论、计算几何、设计理论和代数组合学的方法，这些方法是我研究的主要工具。******特别地，我想关注（但不限于）ad-hoc、传感器和社交网络。我的目标是建立我的专业知识，开发技术，并回答一些新出现的问题。下面我将简要介绍其中的一些。******1)各种各样的现代网络可能有数百万个节点和连接，事实上，其中许多节点和连接可能一次都不存在。在这样的网络中，利用经典算法求解问题是不可能的。在过去的几年里，针对一些基本问题，已经提出了局部算法，该算法利用机器人在网络上移动，并且在每一步机器人只能使用网络的局部部分。遍历，或s，t-连通性，就是这样一个基本问题，已经被广泛研究了很多年。在一项开创性的工作中，Omer Reingold指出，如果我们知道网络中n个节点的数量，存在一种局部算法，可以在log n空间中解决s，t连接问题。如果我们考虑到额外的信息，例如几何信息（网络节点将具有机器人几何图形可用的坐标），那么可以保证更强的局部遍历。我打算继续这个方向的研究。******2)我开发的一些几何图局部遍历技术要求几何图满足一定的结构条件。我建议通过强加一个由虚拟节点和连接组成的“虚拟”网络来放宽这一条件，该网络将由机器人在其内存中构建，并保证满足两个网络“联合”的结构条件。虚拟网络将是规则的，例如网格，以便可以计算并与现有网络的局部部分合并。这是一种新的方法，我相信它将在以本地方式解决许多网络问题方面非常有用。******3)迷宫遍历算法在文献中得到了广泛的研究。随着当前技术的出现和对室内地图和导航的倡议，这种算法越来越受欢迎。我建议研究在迷宫未知或机器人在迷宫中的位置未知的情况下，使用非常简单和有限的机器人穿越迷宫的问题。

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.