During the past decade there has been tremendous interplay among discrete mathematics, theoretical computer science, probability theory, and statistical physics. This project brings together researchers from these various fields to explore topics at their interface, the field coming to be called Discrete Random Systems. The focus is on probabilistic algorithms and models that arise in the study of physical systems and combinatorial structures, with strong themes running through these interactions including: phase transitions; probabilistic combinatorics; Markov-Chain Monte Carlo and other random walks; and random structures and randomized algorithms. A series of workshops will address properties of large graphs, complex networks and applications, Markov chain sampling (theory vs. practice), and phase transitions in random structures. Focused working groups of researchers will concentrate on the interface between Markov chains and phase transitions, on heuristic and rigorous approaches to identifying and analyzing phase transitions in algorithms.
Discrete Random Systems is a relatively new field that solidified during an interdisciplinary series of workshops held at the DIMACS Center and the Institute for Advanced Study ten years ago. Since then it has matured considerably, and the truly bilateral exchange between discrete mathematicians and theoretical computer scientists on the one hand, and probabilists and statistical physicists on the other, has radically impacted research directions and understanding in all of these fields. The field explores algorithms and models that arise in both the study of physical systems and the mathematical structures arising from the fields of combinatorics and theoretical computer science, with an emphasis on analogous behavior such as phase transitions. The current project seeks to foster and speed the development of this interdisciplinary field and to bring to it coherence as well as rapid scientific development. The project will be organized around a series of workshops, tutorials, research working groups, and a visitor program, all intended to facilitate new interactions. Workshops allow a cross-fertilization of ideas and techniques from the disparate disciplines. Less formal groups of researchers will convene for concentrated collaborative research on specialized topics, and additional working groups will evolve during the project. Exploration of new areas of application of Discrete Random Systems will be enhanced by parallel DIMACS programs in Biology, Epidemiology, the Social Sciences, and Homeland Security. The ideas developed in this project will have impact on a myriad of fields and create many new cross-disciplinary connections. A visitor program will encourage senior and junior researchers, including students, to participate in collaborative research spawned by the workshops and in the work of the working groups. Each workshop will have a fund for support of graduate students and postdocs and workshops will have a substantial educational component through significant tutorial components. The topic lends itself well to undergraduate research and participating faculty will coordinate topics with an undergraduate research program (REU program) already in existence. The project is expected to have a long-term impact well beyond its two year duration since the workshop, working group, visitor, and dissemination components of the project will allow the ideas developed to reach hundreds of people nationwide and worldwide. The project should significantly influence the careers of a large number of outstanding junior researchers and it should play an important role in the training and development of scientists who are well-prepared to become leaders in the field of Discrete Random Systems.
