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

合作研究：AF：小：差异理论的新方向和方法

• 批准号: 2327010
• 负责人: Sahil Singla
• 金额: $ 30万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-10-01 至 2026-09-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2327010&HistoricalAwards=false
• 关键词: Collaborative; Research; AF; Small; New

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.

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