CAREER: Sharp Concentration and Probabilistic Methods

在这项建议中，PI解决了概率组合数学中一些最深和最重要的问题，包括尖锐的浓度不等和半随机方法。Pi和他的合作者计划建立新的尖锐的集中不等式，并将它们与强大的半随机(Rodl Nibble)方法一起应用于攻击组合数学中几个著名的和长期存在的猜想。其中，PI将研究一系列有限几何中的极小轴问题，这是在50年代提出的。另一个主题是随机物体的几何性质的研究。这里有一个典型的问题：一个人需要多少个点才能穿透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.