AF: Small: Rare Events - New Probabilistic and Algorithmic Techniques

University Of California-San Diego, La Jolla CA

Investigators

Abstract

Randomness is a powerful tool in mathematics and computer science. In mathematics, it underlies the "probabilistic method," a method to prove that certain mathematical objects with desired properties exist, by simply picking an object at random, and arguing that with a positive probability, the object has the required properties. In computer science, randomness is a powerful tool in algorithm design. Randomized algorithms are often simpler or perform better than their deterministic counterparts, and have found applications in many fields such as graph algorithms, linear programming, routing algorithms, coding theory, communication protocols, approximation algorithms, cryptography, and many more. One of the main reasons that randomness is ubiquitous in algorithm design, is that typically the probabilistic method shows that the desired events, which control the success of the algorithm, not only occur with a positive probability (which would be sufficient to prove existence), but that they in fact occur with overwhelming probability. As such, it immediately lends itself to the design of randomized algorithms. The focus of this project is on regimes where this is not the case. There are several probabilistic techniques which can prove the existence of "rare events." That is, they show that the desired events occur with a positive (yet tiny) probability. Although we do not have many such techniques, they have proven to be extremely valuable, with applications in many domains: combinatorial optimization, learning theory, approximation algorithms, distributed algorithms, computational geometry, numerical analysis, and more. The main reason is that such techniques, and more importantly, their algorithmic realizations, provide algorithm designers with new sets of tools that they can apply that go beyond "vanilla" probabilistic techniques. This project will focus both on the development of new mathematical and algorithmic tools and techniques, as well as on their assimilation by students and researchers. This involves mentoring students, creating and teaching relevant classes, writing expository surveys, and organizing workshops. On the technical side, the project focuses on two main domains. The first is discrepancy theory. Discrepancy theory studies irregularities within distributions, and has intimate relations with rounding techniques for integer programs, and more generally with combinatorial optimization. There are several important open problems in discrepancy theory (most notably the Komlos conjecture), which this project sets a concrete plan to resolve. The second domain is pseudo-randomness. Pseudo-randomness is the study of deterministic objects which attain certain properties satisfied by random objects. As such, this is a wide area of study, with many applications both in mathematics and computer science. In this project, we focus on pseudorandom objects which, for some bounded family of tests, behave exactly like random objects. While in some settings such objects are deeply understood and widely applied (for example, k-wise independence, which has applications in coding theory, data structures, de-randomization, and more), in many other settings they are much less understood. This project explores new approaches to better understand such objects and to develop new algorithmic applications of them.