During the past decade there has been tremendous interplay between discrete mathematics, theoretical computer science, and statistical physics. This project brings together researchers from these various fields to explore topics at their interface. The focus is on probabilistic algorithms and models that arise in the study of physical systems and combinatorial structures. Strong themes running through these interactions include: phase transitions; probabilistic combinatorics; Markov Chain Monte Carlo and other random walks; and random structures and randomized algorithms.

The active participation of scientists across disciplines in this area of *Discrete Random Systems* is indicative of the rich potential for further ground-breaking cross-fertilization. There has already been significant impact from these recent interactions. Physicists are gaining insights into physical systems, and in particular the simulations of these systems, through complexity theory and new algorithmic paradigms developed by computer scientists and discrete mathematicians. Computer scientists are gaining a much richer understanding of computational possibilities, and computational limitations, by considering the physical implications of their inquiries. Discrete mathematicians are developing new tools for studying large combinatorial systems by looking at infinite analogues studied in physics and applying randomized computational methods.

This area is of increasing commercial, economic, and societal relevance as large-scale real-world systems are successfully modeled stochastically. Examples of these diverse applications include discrete models of biological epidemics, structural analysis of the world-wide web, and stochastic optimization methods for operations research problems in transportation and scheduling.

The DIMACS special focus on Discrete Random Systems will bring together world class researchers working at the interface between discrete probability, statistical physics, and computer science, graduate students in these different disciplines, and practitioners working in various application domains. The program will explore a broad spectrum of topics in the emerging field of Discrete Random Systems through a series of focused workshops, research working groups, and a visitor program, all intended to facilitate new interactions. More specifically, throughout the program we plan to address open problems and applications for each of the following:

- Randomized algorithms for combinatorial, decision, optimization, and enumeration problems.
- Random structure such as random graphs and random CNF Formulas, including questions of existence, optimization, and connections between phase transitions and computational intractability.
- Probabilistic combinatorics including extremal combinatorics and the new field of quasi-random graphs.
- Phase transitions in discrete physical systems and percolation models from statistical physics.
- Rapid and torpid mixing of Markov Chain Monte Carlo (MCMC) processes in finite-sized physical systems and combinatorial models.
- Technical tools used in the above, including mathematical methods (e.g., martingales, large-deviation inequalities, conductance and related measures) and physics tools (e.g., the replica and cavity methods).
- Optimization and analysis for real-world problems that may be modeled by random structures, including the Internet and biological structures.

The physicist's notion of a phase transition in an infinite system can often be related to a computer-science notion of slow mixing, and there are general theorems to convert between the two views. Jerrum and Sinclair's "conductance" bound on mixing rate is a version of Cheeger's inequality, and there are a host of other methods for bounding mixing times that arise in other contexts in statistical physics. A version of the Lovasz Local Lemma, a result in probabilistic combinatorics, has been related to Dobrushin's inequality in physics. A prototypical exact but non-rigorous physical result for a combinatorial problem, random assignment, has been paralleled by rigorous probabilistic and combinatorial methods, and new combinatorial problems, notably the SAT phase transition, have been addressed by new non-rigorous results in statistical physics. The field is advancing now at the greatest rate imaginable, and the special focus will help identify and promote directions offering the most impact. The timing for this program could not be better.

This special focus is a natural follow-up to a program at the MSRI on *Probability, Algorithms and Statistical Physics*, January 3, 2005 to May 13, 2005, with organizers David Aldous, Claire Kenyon, Harry Kesten, Jon Kleinberg, Fabio Martinelli, Yuval Peres (co-chair), Alistair Sinclair (co-chair), Alan Sokal, Peter Winkler, and Uri Zwick. The timing of this special focus was chosen so as to provide a breathing space between the activities at the MSRI and DIMACS while maintaining momentum and enabling further collaborations in this growing research area, and to connect to activities at DIMACS in Biology, Epidemiology, the Social Sciences, and homeland security that will drive the field in new directions.

This special focus will differ from the MSRI program by emphasizing small working groups, formal and informal, that will delve in detail into some of the topics expected to come up during the MSRI semester. Workshops will lay the groundwork for these intense, collaborative working groups.

The DIMACS program will have a broader computer science focus than the MSRI program. During the semester at MSRI, the general theme is connections between theoretical compute science and mathematical physics, including phase transitions in the web graph. At DIMACS we expect to explore other topics in computer science where discrete random systems are currently playing a central role, including computational applications in the biological sciences. A workshop will foster collaborations between theoreticians and practitioners using Markov chain sampling methods to study large data sets. Interactions with other DIMACS activities such as the multi-year special foci on Computational and Mathematical Epidemiology, Information Processing in Biology, and Computation and the Socio-economic Sciences will provide additional directions for collaborations involving connections between discrete random systems and many applications.

Index of Special Focus on Discrete Random Systems

DIMACS Homepage

Contacting the Center

Document last modified on June 4, 2009.