CAREER: Sharp Concentration and Probabilistic Methods

DMS-0239316 Van V. Vu在这个提案中，PI解决了概率组合学中一些最深刻和最重要的问题，包括sharpconcentration不等式和半随机方法。 PI和他的合作者计划开发新的尖锐浓度不等式，并将其与强大的半随机（Rodl nibble）方法一起应用于攻击组合学中几个著名的长期存在的问题。其中，PI将研究一系列的minimax问题，在有限几何，提出了在五十年代。另一个主题是随机物体几何性质的研究。下面是一个典型的问题：在单位区间的d个随机子区间的笛卡尔积中得到一个随机盒子，需要多少个点才能刺穿n个随机d维盒子？ PI还计划使用概率组合学的方法来解决编码理论和“真实世界”图研究等非常实际的领域中出现的问题。出于教育目的，他打算写一本关于集中不等式及其在组合学和理论计算机科学中的应用的教科书。他还计划在加州大学圣地亚哥分校设计和教授一门关于概率方法的研究生课程。在过去的二十年里，概率论已经成为离散数学和计算机科学中最强大的武器之一。 第一个主要原因是随机性帮助我们克服了确定性方法无法解决的算法和存在性问题。第二个主要原因是，许多重要的现实生活中的对象（如互联网）可以通过随机过程建模。 另一方面，在许多情况下，问题是如此复杂，传统的结果从概率论不能应用。PI计划开发新的概率工具，这将对许多此类问题产生突破性的影响，其中一些问题已经开放了几十年。除此之外，这些新工具将帮助我们设计非常有效的随机算法，证明有趣对象的存在，并分析复杂的过程。 出于教育目的，PI打算编写一本关于离散概率及其在离散数学和理论计算机科学中的应用的教科书。

DMS-0239316Van V. VuIn this proposal, the PI addresses some of the deepest and mostimportant issues in probabilistic combinatorics, including sharpconcentration inequalities and the semi-random method. The PI and hiscollaborators plan to develop new sharp concentration inequalities andapply them, together with the powerful semi-random (Rodl nibble) methodto attack several well-known and long standing conjectures incombinatorics. Among others, the PI will study a series of minimaxproblems in finite geometry, raised in the fifties. Another topic is thestudy of geometrical properties of random objects. Here is a typicalquestion: how many points does one need to pierce n random d-dimensionalboxes, where a random box is obtained as the Cartesian product of drandom subintervals of the unit interval ? The PI also plans to usemethods from probabilistic combinatorics to attack problems arose fromvery practical fields such as coding theory and the study of"real-world" graphs. For educational purposes, he intends to write atextbook on sharp concentration inequalities and its applications incombinatorics and theoretical computer science. He also plans to designand teach a graduate course at UCSD on the probabilistic methods. In the last twenty years, probability has become one of the mostpowerful weapons in discrete mathematics and computer science. Thefirst main reason is that randomness helps us to overcome algorithmicand existence problems which cannot be solved deterministic means. Thesecond main reason is that many important real-life objects (such as theinternet) can be modeled by a random process. On the other hand, inmany situations, the problems are so complex that traditional resultsfrom probability theory cannot be applied. The PI plans to develop newprobabilistic tools which would have a break-thought impact on many suchproblems, some of them have been open for decades. Among others, thesenew tools would help us to design very efficient randomized algorithms,to prove the existence of interesting objects, and to analyzecomplicated processes. For educational purposes, the PI intends towrite a textbook on discrete probability and its applications indiscrete mathematics and theoretical computer science.