CAREER: Fundamentals of Random Discrete Systems

This project will develop foundational techniques to study fundamental phenomena around random discrete systems. Random discrete systems, such as random graphs, are central across mathematics, computer science, statistics, and practical applications. Phenomena around random systems, such as the emergence of structures or the threshold phenomena, have been a fundamental subject in combinatorics and probability, with influential connections to geometry, computer science, number theory, and analysis. The project serves the national interest by promoting the progress of science, strengthening mathematical foundations for large networks and random systems with connections to important applications including artificial intelligence and quantum information, and training students in areas important to future scientific and technological innovations. It will also foster interdisciplinary connections through conferences and summer schools bridging mathematics and computer science, and will broaden participation and support education through new courses, lecture notes, tutorials, and mentoring opportunities for graduate, undergraduate, and high school students. More precisely, the project has two main research directions. The first direction is to develop foundational techniques to address fundamental gaps in the current understanding of phenomena around thresholds and first moment obstructions. The project will also develop new toolkits to study first moment obstructions, thus facilitating new applications of advances on the threshold phenomena, and will extend the theory beyond the Boolean lattice to more general settings, such as random subspaces of finite vector spaces, which are useful for cryptography applications. Leveraging the PI’s expertise on controlling first moment obstructions and demonstrating their fundamental role in probabilistic phenomena, the project will strengthen the connections between the threshold phenomena, suprema of stochastic processes and large deviations phenomena, all of which are foundational to important random processes and systems, such as large random networks, and neural networks with large widths in artificial intelligence. The second direction of the project is to study random systems with substantial structure and dependency, especially random Cayley graphs and other dependent random graph models. These models arise naturally in additive combinatorics, spectral graph theory, high-dimensional expanders, information theory, and lay the foundation to applications such as constructions of quantum codes. The project will develop techniques to address important open questions around random Cayley graphs, which also simultaneously provide new combinatorial and probabilistic approaches to study sets with small doubling and important questions in additive combinatorics. 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 Award ID: 2543870 | Program: 01002930DB NSF RESEARCH & RELATED ACTIVIT,01003031DB NSF RESEARCH & RELATED ACTIVIT,01002627DB NSF RESEARCH & RELATED ACTIVIT | Principal Investigator: Huy Pham | Institution: California Institute of Technology, PASADENA, CA | Award Amount: $299,999 View on NSF Award Search: https://www.nsf.gov/awardsearch/show-award/?AWD_ID=2543870 View on Research.gov: https://www.research.gov/awardapi-service/v1/awards/2543870.html