DIMACS/Georgia Tech Special Focus on Discrete Random Systems

点击翻译按钮获取中文摘要

During the past decade there has been tremendous interplay amongdiscrete mathematics, theoretical computer science, probabilitytheory, and statistical physics. This project brings togetherresearchers from these various fields to explore topics at theirinterface, the field coming to be called Discrete Random Systems.The focus is on probabilistic algorithms and models that arise inthe study of physical systems and combinatorial structures, with strongthemes running through these interactions including: phase transitions;probabilistic combinatorics; Markov-Chain Monte Carlo and otherrandom walks; and random structures and randomized algorithms.A series of workshops will address properties of large graphs, complexnetworks and applications, Markov chain sampling (theory vs. practice),and phase transitions in random structures. Focused working groups ofresearchers will concentrate on the interface between Markov chainsand phase transitions, on heuristic and rigorous approaches to identifyingand analyzing phase transitions in algorithms.Discrete Random Systems is a relatively new field that solidifiedduring an interdisciplinary series of workshops held at the DIMACSCenter and the Institute for Advanced Study ten years ago. Since thenit has matured considerably, and the truly bilateral exchange betweendiscrete mathematicians and theoretical computer scientists on the onehand, and probabilists and statistical physicists on the other, hasradically impacted research directions and understanding in all ofthese fields. The field explores algorithms and models that arise inboth the study of physical systems and the mathematical structuresarising from the fields of combinatorics and theoretical computerscience, with an emphasis on analogous behavior such as phasetransitions. The current project seeks to foster and speed thedevelopment of this interdisciplinary field and to bring to itcoherence as well as rapid scientific development. The project willbe organized around a series of workshops, tutorials, research workinggroups, and a visitor program, all intended to facilitate newinteractions. Workshops allow a cross-fertilization of ideas andtechniques from the disparate disciplines. Less formal groups ofresearchers will convene for concentrated collaborative research onspecialized topics, and additional working groups will evolve duringthe project. Exploration of new areas of application of Discrete RandomSystems will be enhanced by parallel DIMACS programs in Biology,Epidemiology, the Social Sciences, and Homeland Security. The ideasdeveloped in this project will have impact on a myriad of fields andcreate many new cross-disciplinary connections. A visitor program willencourage senior and junior researchers, including students, toparticipate in collaborative research spawned by the workshops and inthe work of the working groups. Each workshop will have a fund forsupport of graduate students and postdocs and workshops will have asubstantial educational component through significant tutorialcomponents. The topic lends itself well to undergraduate research andparticipating faculty will coordinate topics with an undergraduateresearch program (REU program) already in existence. The project isexpected to have a long-term impact well beyond its two year durationsince the workshop, working group, visitor, and disseminationcomponents of the project will allow the ideas developed to reachhundreds of people nationwide and worldwide. The project shouldsignificantly influence the careers of a large number of outstandingjunior researchers and it should play an important role in thetraining and development of scientists who are well-prepared to becomeleaders in the field of Discrete Random Systems.