Theoretical Computer Science and Discrete Mathematics (CSDM)
Welcome to the home page of the special program in Theoretical Computer Science and Discrete Mathematics (CSDM). The main purpose of this program is intensive research, often in cooperation with short-term visitors and nearby academic and research institutions. The CSDM program has two weekly seminars. Previous activities of the CSDM program can be found through links on the sidebar to the right.
To learn more about this program and our activities, follow one of these links or read the background information below.
Theoretical Computer Science is one of the most vibrant and active areas of scientific study today. Starting half a century ago, even before computers existed, theorists set out to define mathematically the concept of "computation," and to study its power and limits. The theoretical discoveries of Alan Turing, John von Neumann (Institute faculty member, 1933-57) and their contemporaries led to the practical construction of the first stored program computer at the IAS, followed by the computer "revolution" we are witnessing today. Simultaneously, researchers found unexpected mathematical depth in the theory of computation, which has matured into a rich and beautiful field, made deep connections to other areas, and attracted talented young scientists.
Discrete Mathematics---the study of finite structures---provides a framework for the rigorous study of computation, and is also a flourishing field in its own right. Over the last century it has developed many fascinating problems along with an arsenal of powerful techniques, and enjoys a rich interplay with Theoretical Computer Science.
For more in-depth information and perspectives on these fields' development, please explore our collection of essays.
IAS faculty members John von Neumann (1933-57) and Kurt Godel (1953-76) made central contributions to the birth of Theoretical Computer Science. The School of Mathematics began to reengage with this stream of research in the early 1990s with a well-received series of lectures and seminars. In 1997-98 and 1998-99, Noga Alon and Avi Wigderson assumed the leadership of further programs in Discrete Mathematics and Theoretical Computer Science, and Avi Wigderson was appointed to a newly-created faculty position in 1999. This marked the formal beginning of the CSDM special program, which has since hosted many postdocs and leading senior researchers.
Collaborations and Education
From its beginning, the CSDM Program has worked in close collaboration with near-by academic establishments and industry research groups. Our principal collaborators include:
- Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)
- Department of Computer Science at Princeton University
- The Center for Computational Intractability
- NEC Research Institute
The Program puts a special stress on educational aspects. Every year the Program seeks postdoctoral applications from graduating Ph.D.s in the areas of Theoretical Computer Science and Discrete Mathematics. Under the auspices of IAS/Park City Institute, in the summer of 2000 Avi Wigderson and Steven Rudich (Carnegie-Mellon) organized a Graduate Summer School in Computational Complexity. IAS members have also contributed to a number of workshops and minicourses offered at the Center for Computational Intractability.