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.