Applications of random graphs and walks

我的研究是跨学科的。我工作的中心主线集中在组合学和CS理论、算法复杂性和具体应用的问题上。概率论在我的大部分工作中发挥了作用，我经常专注于随机化，它对问题的影响，以及算法的好处。随机图(网络)和随机行走经常出现在我的作品中。随机网络是普遍存在的问题，也是概率论和组合学中的经典研究课题。它们的重要性源于作为许多自然现象的模型，从社会网络和社区内的相互作用，通过计算机网络，到种群谱系的模型，以及复杂生物系统中蛋白质的相互作用。因此，网络分析在许多领域有着广泛的应用。随机游走同样很常见，既是自然发生过程的模型，也是工具。我研究的第二个主题涉及随机环境下的优化问题。虽然一些算法在最坏的情况下可能表现不佳，但它们在典型情况下可能表现得更好。最近，我们给出了在具有随机边权的图上寻找最大割的局部最大值的翻转算法运行时的第一个多项式界。许多基本问题仍然悬而未决：多项式的最佳次数是多少？目前的范围在1到9.3之间。如果我们不允许一次翻转一个顶点，而是允许翻转两个顶点，会怎么样？这里只有准多项式界是已知的。那Max-k-Cut呢？还有许多其他的组合优化问题，其中的复杂性是未知的，我计划研究。我还研究计算生物学中的问题。我们开发了一种基于随机行走的算法，用于从现代单细胞RNA计数中提取具有生物学意义的见解。将数据拟合到低维流形上；利用样本的邻近度在样本点上生成图形，并分析其结构。出现了许多概率和算法项目：设计方法来生成对数据中的各种噪声源更健壮的图形，开发新的算法来定位图形中的模式，简化这些算法，以便能够分析更大的数据集，等等。这些反馈到实验设计中。另一个话题是关于土匪问题的变种。代理每次选择几个操作中的一个，并收到报酬。目标是让代理人从观察到的收益中确定最优行动。这个问题已经有了广泛的文献和应用，但许多自然变异还没有被很好地理解。假设有几个代理独立做出决策，如果他们选择相同的操作，则会受到惩罚。根据代理是否在冲突发生时看到它们，以及它们是否被允许通信，会有不同的情况。在信息量最小的模型中，即使对于I.I.D.，预期的最优后悔也是以多项式增长的。收益向量，但最优指数未知。

My research is interdisciplinary. Central threads of my work focus on questions from combinatorics and CS theory, algorithmic complexity and concrete applications. Probability theory plays a role in the vast majority of my work, and I often focus on randomization, its effects on a problem, and benefits in algorithms. Random graphs (networks) and random walks feature often in my work. Random networks are ubiquitous and a classical research topic in probability theory and combinatorics. Their importance stems from being a model of many natural phenomena, from social networks and interaction within communities, through computer networks, to models for genealogy of populations, and interactions of proteins in complex biological systems. Thus network analysis has a multitude of applications in many areas. Random walks are similarly common, as a model for naturally occurring processes and as a tool. A second theme of my research involves problems of optimization in random settings. While some algorithms may behave badly in the worst case, they may do better in typical settings. Recently we gave the first polynomial bound on the runtime of the FLIP algorithm for finding the a local maximum for MAX-CUT on a graph with random edge weights. Numerous fundamental questions remain open: What is the optimal polynomial degree? Current bounds are between 1 and 9.3. What if we allow flipping not one vertex at a time, but two? Only quasi-polynomial bounds are known here. What about MAX-k-CUT? There are numerous other combinatorial optimization problems, where the complexity is unknown, which I plan to study. I also work on problems from computational biology. We developed an algorithm based on random walks for extracting biologically meaningful insights from modern single cell RNA counts. Data is fitted onto a low dimension manifold; Proximity of the samples is used to generate a graph on the sample points, and its structure is analyzed. Many probabilistic and algorithmic projects arise: Devise ways to generate graphs that are more robust to the various sources of noise in the data, develop new algorithms to locate patterns in the graph, simplify these so that analysis of larger data sets becomes feasible etc. These feed back into experimental design. Another topic is variants on the bandit problem. An agent selects at each time one of several actions and receives a payoff. The goal is for the agent to identify from observed payoffs the optimal action. This problem has extensive literature and applications, yet many natural variations are not well understood. Suppose there are several agents who make decisions independently, with a penalty if they select the same action. There are variations depending on whether agents see collisions as they occur, and whether they are allowed to communicate. In the least informative model, the expected optimal regret is known to grow polynomially even for i.i.d. payoff vectors, but the optimal exponent is not known.