Mathematical Sciences: Probability and Statistics Applied tothe Theory of Algorithms

该项目将在算法、经验过程和随机图的概率分析的三个广泛领域探索七个明确的猜想。这些明显不同的领域之间的几个联系将被澄清并用在猜想的解中。Karp关于旅行商问题的概率多项式时间算法，引出了对具有特殊性质的随机图的考虑。因此，旅行商问题的中心极限定理和大偏差理论与极小生成树、极小匹配等随机图论中的关注量有关。使用的一些新技术包括Sobolov不等式理论和Efron-Stein不等式。随机树理论是通过给n个顶点的树赋予特定的概率分布而发展起来的。它将表明，哈珀方法的使用导致了更丰富的随机树理论。哈珀的方法反过来又导致了与线的经验过程的联系。这项研究的新颖性在于其问题驱动的方法，以及对看似不同的领域之间的相互联系的阐明和开发。

The project will explore seven explicit conjectures in three broad areas of probabilistic analysis of algorithms, empirical processes and random graphs. Several connections between these apparently different areas will be clarified and used in the solutions of the conjectures. Karp's probabilistic polynomial time algorithm for the traveling salesman problem, leads to considerations of random graphs with special properties. Thus the central limit theorem and the large deviation theory of the traveling salesman problem have connections with quantities of interest in the random graph theory such as minimal spanning trees, and minimal matchings. Some of the new techniques used include the theory of Sobolov inequalities and the Efron-Stein inequality. Theory of random trees is developed by putting specific probability distributions on the trees with n vertices. It will be shown that the use of Harper's method leads to a richer theory of random trees. Harper's method in turn leads to connections with the empirical process of lines. The novelty of the research is its problem-driven approach and the elucidation and exploitation of the interconnections of seemingly divergent fields.