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.

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