Theoretical Computer Science and Discrete Mathematics (CSDM)
|
Sponsored by:
|
Abacus |
"Analytical Engine" |
Turing Machine |
If you would like to learn about this program and our activities, follow one of these links or read the background information.
- Theoretical Computer Science and Discrete Math Seminars
- Current Members
- Postdoctoral Positions
- NSF Grants:
Pseudorandomness
The Center for Computational Intractability - Related near-by seminars
- Useful links
The CSDM program, which is in its 11th year, has two weekly seminars. The main purpose of this program is intensive research, often in cooperation with short-term visitors and local people from academic and research institutions such as Princeton University, The Center for Computational Intractability, Rutgers University, DIMACS or AT&T. For more information, check out the pages Seminars and People.
Previous activities of the CSDM program can be found through the links listed in the sidebar to the right.
Background Information
General
Welcome to the home page of the special program in Theoretical Computer Science and Discrete Mathematics (TCS/DM).
This field is one of the most vibrant and active areas of scientific study today. Starting half a century ago, even before computers existed, theoretical computer scientists 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.
The practical use of computers and, simultaneously, the unexpected mathematical depth of the abstract notion of "computation" have significantly altered and expanded theoretical computer science. In the last quarter century it has turned into a rich and beautiful field, making connections to other areas and attracting talented young scientists. More technical (but still popular) descriptions of various related aspects can be found in these brief essays:
- Some aspects of the evolution undergone by Theoretical Computer Science in the last quarter century
- On relations between TCS and other sciences
- Discrete Mathematics: Past, Present and Future
as well as in the comprehensive article
- P, NP and Mathematics - a computational complexity perspective
written by Avi Wigderson for the Proceedings of the International Congress of Mathematicians in Madrid (2006).
TCS/DM at the Institute
The "parent" disciplines from which Theoretical Computer Science and Discrete Mathematics evolved were once represented at the Institute by John von Neumann (1933-57) and Kurt Godel (1953-76). After a considerable gap, the School of Mathematics began to explore the possibility of re-opening this stream of research in the early 1990s with a well-received series of lectures given by Michael Rabin and Richard Karp. The year 1993 marked the opening of a series of exploratory programs led by various leading researchers from all over the world. In the same year the weekly seminar (now known as Theoretical Computer Science and Discrete Math Seminar) was established.
The exploratory programs proved to be quite successful, both scientifically and educationally, and also were well-received by the mathematical community outside the Institute. Thus, it was decided to go ahead, and in 1997-98 and 1998-99, Noga Alon and Avi Wigderson assumed the leadership of further programs in combinatorics and computational complexity.
A commitment to the permanent presense of Theoretical Computer Science and Discrete Mathematics was made by appointing Avi Wigderson to the newly created faculty position (1999). This event also marks the formal beginning of the TCS/DM special program.
Almost immediately (in the academic year of 2000-01) the Program was holding a Special Year on Computational Complexity that attracted well-known researchers in this field. As another part of the effort to get it established, Alexander Razborov was appointed to be in residence as a senior member in 2001-2006.
Previous activities can be found through the links listed in the sidebar above under previous years.
Collaborations and Education
From its very beginning, the CSDM Program has been working in close collaboration with near-by academic establishments, as well as with industry research groups. The list of our principal collaborators in particular includes:
- 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. 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. Every year the Program seeks postdoctoral applications from graduating Ph.D.s in the areas of Theoretical Computer Science and Discrete Mathematics.
- More information on Postdoctoral positions
Return to the top of this page
- Printer-friendly version
- PDF version