Algorithmic problems emerging in new networking technologies

在过去的几年里，我的研究兴趣集中在三个主要领域：互连网络通信的理论方面和算法、计算生物学和图论。在未来，我预计将继续活跃在这三个领域，但我将专注于与第一个领域相关的问题，因为从引人入胜的新技术中出现的问题经常使用组合学、图论、计算几何、设计理论和代数组合学的方法，这些都是我研究的主要工具。我的目标是以我的专业知识为基础，开发技术，并回答一些新出现的问题。我在下文中简要描述其中的一些。1)所有类型的现代网络可能有数百万个节点和连接，事实上，它们中的许多甚至可能不同时存在。利用经典算法来解决此类网络上的问题是不可能的。在过去的几年里，已经针对几个基本问题提出了本地算法，即利用机器人在网络上移动，并且在每一步机器人只能使用网络的局部部分。遍历，或S，t-连通性，就是这样的基本问题之一，多年来一直被广泛研究。在一项开创性的工作中，Omer Reingold证明了如果我们知道网络中的节点数n，就存在一个局部算法来求解Logn空间中的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.