Collaborative Research: CCF: AF: Small: New Frontiers in Structures vs Randomness with Applications to Combinatorics, Complexity, Algorithms

A prominent paradigm used in both mathematics and computer science is the “structure vs randomness'' paradigm. At one end, it aims to identify structure in mathematical objects that is useful for their mathematical analysis and for the design of efficient algorithms for their manipulation. At the other end, it aims to use randomness and random-like properties for the analysis of objects that lack structure. Randomness is a common mathematical tool used throughout mathematics and computer science. One can sometimes identify “random like'' properties of mathematical objects that are as useful as true randomness for their study and analysis. In the best-case scenario, randomness can be identified as the absence of structure, and the two notions of structure and randomness can be seen as complementary. The project will expand the bridge between mathematics and computer science and may have a practical impact on widely adopted algorithms. Integration of research and education is a key component of the project. This project focuses on a novel approach towards this “structure vs randomness'' paradigm, whose main goal is to obtain significantly improved quantitative bounds for many important problems in mathematics and computer science. At the core of this new paradigm are two new concepts: spreadness and mixing. Spreadness is a quantification that there are not too many elements in any structured subset of the ambient universe and mixing is a measure for how two objects behave jointly via some common operation. The project aims to develop both the theory and applications of this new approach. On the theory side, we aim to build a versatile framework that can both connect existing applications and extend them to new ones. On the applications side, the proposal highlights exciting potential applications across several fields - additive combinatorics, communication complexity, graph theory, and fast combinatorial algorithms. 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.