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的法定任务，并使用基金会的知识分子优点和更广泛的影响审查标准，被认为值得通过评估来获得支持。