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

Regents Of The University Of Michigan - Ann Arbor, Ann Arbor MI

Investigators

Abstract

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.