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

AF：小：罕见事件 - 新的概率和算法技术

• 批准号: 1614023
• 负责人: Shachar Lovett
• 金额: $ 45万
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-07-01 至 2020-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1614023&HistoricalAwards=false
• 关键词: AF; Small; Rare; Events; New

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.

随机性是数学和计算机科学方面的强大工具。在数学中，它是“概率方法”的基础，即一种方法，证明存在具有所需属性的某些数学对象，只需随机选择对象，并以正概率为基础，该对象具有所需的属性。在计算机科学中，随机性是算法设计中的强大工具。 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控制算法成功的事件，不仅出于正概率（足以证明存在），而且实际上它们实际上是出于压倒性的概率。因此，它立即将自己借助随机算法的设计。该项目的重点在于事实并非如此。有几种概率技术可以证明存在“罕见事件”。也就是说，他们表明所需的事件以正（但很小）的概率发生。尽管我们没有许多这样的技术，但事实证明它们在许多领域中都非常有价值：组合优化，学习理论，近似算法，分布式算法，计算几何形状，数值分析等。主要原因是，此类技术，更重要的是它们的算法实现，为算法设计师提供了新的一组新工具，它们可以应用于“ Vanilla”概率技术之外。该项目将重点介绍新的数学和算法工具和算法工具和技术，以及学生和研究人员和研究人员和研究人员的发展。这涉及指导学生，创建和教授相关课程，编写说明性调查以及组织研讨会。在技术方面，该项目着重于两个主要领域。第一个是差异理论。差异理论研究了分布中的不规则性，并且与整数程序的舍入技术有着密切的关系，更普遍地通过组合优化。差异理论（最著名的是科姆洛斯猜想）中有几个重要的开放问题，该项目为解决方案设定了解决方案。第二个领域是伪随机。伪随机度是对确定对象的研究，该对象获得了随机对象满足的某些属性。因此，这是一个广泛的研究，在数学和计算机科学中都有许多应用。在这个项目中，我们专注于伪随机对象，对于某些有界的测试家族，其行为与随机对象完全一样。尽管在某些情况下，这种对象得到了深入的理解和广泛应用（例如，K-Wise独立性，它在编码理论，数据结构，De-Mandanmization等方面都有应用，在许多其他设置中，它们的理解程度不高得多。该项目探讨了更好地理解此类对象并开发其新算法应用程序的新方法。