Collaborative Research: AF: Small: New Directions and Approaches in Discrepancy Theory

差异理论是一个跨学科的领域，它是不同学科之间思想交流的桥梁，这些学科包括组合学、概率论、量子计算、凸几何、计算机科学、统计物理和优化。它的主要关注点是将一组对象划分为两个或更多尽可能相似的部分。在过去的二十年里，对差异理论的理解在几个方向上都取得了重大进展。其中包括开发新的算法技术，建立与概率和凸几何的联系，以及探索在理论计算机科学中的应用。这个项目的动机是这些最新的进展，目的是调查差异理论中的新方向。它包括确定这些领域中的关键公开问题，并提出解决这些问题的有前景的方法。这项研究的结果可能会对资源分配、随机对照试验、差异隐私、调度和机器学习等应用产生直接影响。该项目还将培养研究生。尽管差异理论起源于数学，但已经出现了几个与理论计算机科学有关的有趣联系，包括计算几何、伪随机性、近似算法、数值积分、机器学习和整数规划。这个项目特别关注差异研究的三个新兴方向：(I)在线/动态差异，它处理对象随时间变化的情况；(Ii)前缀差异，它需要平衡对象的每个前缀；以及(Iii)超越最坏情况差异，它涉及从分布中选择的对象或被小随机噪声扰动的对象。这个项目中探索的思想将导致开发用于近似算法的新舍入技术、用于公平划分和装箱的新算法以及更快的数值积分方法。此外，他们将有必要创造跨越上述几个领域的新的数学工具。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Discrepancy theory is an interdisciplinary field that acts as a bridge for cross-fertilization of ideas among various disciplines, including combinatorics, probability, quantum computing, convex geometry, computer science, statistical physics, and optimization. Its primary focus is on dividing a set of objects into two or more parts that are as similar as possible. Over the past two decades, significant progress has been made in understanding discrepancy theory in several directions. These include the development of new algorithmic techniques, the establishment of connections with probability and convex geometry, and the exploration of applications in theoretical computer science. This project is motivated by these recent advancements and aims to investigate emerging directions in discrepancy theory. It involves identifying key open problems in these areas and proposing promising approaches to address them. The outcomes of this research could have immediate implications for applications such as resource allocation, randomized controlled trials, differential privacy, scheduling, and machine learning. The project will also train graduate students.Although discrepancy theory originated in mathematics, several intriguing connections with theoretical computer science have emerged, including computational geometry, pseudo-randomness, approximation algorithms, numerical integration, machine learning, and integer programming. This project specifically focuses on three emerging directions for discrepancy research: (i) online/dynamic discrepancy, which deals with situations where the objects change over time; (ii) prefix discrepancy, which requires balancing every prefix of the objects; and (iii) beyond worst-case discrepancy, which involves objects chosen from a distribution or perturbed by small random noise. The ideas explored in this project will lead to the development of new rounding techniques for approximation algorithms, novel algorithms for fair division and bin packing, and faster numerical integration methods. Furthermore, they will necessitate the creation of new mathematical tools that span across several of the aforementioned areas.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.