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

随机性在数学和计算机科学中是一个强大的工具。在数学中，它是“概率方法”的基础，这是一种证明某些具有所需性质的数学对象存在的方法，只需随机挑选一个对象，并论证具有正概率的对象具有所需的属性。在计算机科学中，随机性是算法设计的有力工具。随机化算法通常比确定性算法更简单或性能更好，并已在许多领域得到应用，如图算法、线性规划、路由算法、编码理论、通信协议、近似算法、密码学等等。随机性在算法设计中普遍存在的主要原因之一是，通常概率方法表明，控制算法成功的期望事件不仅以正概率发生(这将足以证明其存在)，而且实际上以压倒性概率发生。因此，它立即致力于随机算法的设计。这个项目的重点是在不是这样的制度上。有几种概率技术可以证明“罕见事件”的存在。也就是说，它们表明期望的事件以正的(但很小的)概率发生。虽然我们没有很多这样的技术，但它们已经被证明是非常有价值的，在许多领域都有应用：组合优化、学习理论、近似算法、分布式算法、计算几何、数值分析等。主要的原因是，这些技术，更重要的是，它们的算法实现，为算法设计者提供了一套新的工具，他们可以应用这些工具，而不仅仅是普通的概率技术。本项目将专注于新的数学和算法工具和技术的开发，以及学生和研究人员对它们的吸收。这包括指导学生，创建和教授相关的课程，撰写说明性调查，以及组织工作坊。在技术方面，该项目专注于两个主要领域。第一种是差异理论。差异理论研究分布中的不规则性，与整数规划的舍入技术，更广泛地说，与组合优化有密切的关系。在差异理论(最著名的是Komlos猜想)中有几个重要的公开问题，本项目制定了一个具体的计划来解决这些问题。第二个领域是伪随机性。伪随机性是对确定性对象的研究，这些对象达到随机对象所满足的某些性质。因此，这是一个广泛的研究领域，在数学和计算机科学中都有许多应用。在这个项目中，我们专注于伪随机对象，对于一些有界的测试族，它们的行为完全像随机对象。虽然在某些环境中，这样的对象被深入理解并被广泛应用(例如，k向独立性，其在编码理论、数据结构、去随机化等方面有应用)，但在许多其他环境中，对它们的理解要少得多。这个项目探索了新的方法来更好地理解这些对象并开发它们的新算法应用程序。

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.