A Proposal for Research on Random Processes and Algorithms

在过去的十年中，随机过程的定量分析在设计基本计算问题的有效算法方面取得了巨大的进步。国际和平研究所正在继续研究这些想法的应用，并开始研究基于非线性和合作过程的新范式。具体而言，本项目主要集中在以下几个方面：(1)马尔可夫链的混合率分析，及其在统计物理和组合学问题的有效算法中的应用；(2)计数问题的计算复杂性的研究及其关于有效逼近性的分类；(3)非线性随机过程，特别是二次动力系统的算法应用；(3)组合优化中一般随机搜索启发式的理论和实验研究，包括Metropolis算法、模拟退火法和合作过程。

During the past decade, the quantitative analysis of random processes has led to dramatic advances in the design of efficient algorithms for fundamental computation problems. The PI is continuing research on the application of these ideas, as well as beginning to investigate new paradigms based on nonlinear and cooperative processes. Specifically, the project focuses on the following directions: (1) the analysis of mixing rates of Markov chains, with applications to efficient algorithms for problems in statistical physics and combinatorics; (2) the study of computational complexity of counting problems, and their classification with respect to efficient approximability; Algorithmic applications of nonlinear random processes, in particular quadratic dynamical systems; (3) the theoretical and experimental study of general randomized search heuristics in combinatorial optimization, including Metropolis algorithm, simulated annealing, and cooperative processes.