CAREER: Sharp Concentration and Probabilistic Methods

点击翻译按钮获取中文摘要

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.