Applications of random graphs and walks

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

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.