DIMACS, the Center for Discrete Mathematics and Theoretical Computer Science, will hold a Special Focus on Mathematics and the Foundations of Computer and Information Science beginning in September 2000 and going through August 2003.
The rapidly changing world of information, communications, and computation is a stimulus for the development of new models and new concepts lying at the foundation of computer and information science and their development will require ever-closer connections with many methods of mathematics. We will investigate the connections between foundational issues in the computer and information sciences and different branches of mathematics in a series of four ``working'' workshops involving both mathematicians and computer scientists, two per year in each of two years. We will de-emphasize formal talks and emphasize discussion time and opportunities to explore new potential collaborations between computer scientists and mathematicians. We will follow up the workshops with opportunities for participants to meet at DIMACS to pursue the research directions identified.
Themes/Motivation. During the first 30 to 40 years of the computer age, the science of computation and communication has been profoundly and broadly influenced by the models, conceptual framework, and methods developed within theoretical computer science (TCS). For example, the theory of languages and automata led to the development of high level programming languages and compilers; the design and implementation of large databases was fundamentally based on theoretical models; the notion of polynomial time tractability which developed within the field of computational complexity provided a fundamental criterion for algorithmic efficiency that is now universally applied; the field of algorithm design and analysis yielded a large library of practical algorithms, as well as basic principles for attacking new computational problems; the study of private secure communication within computational complexity revolutionized the classical field of cryptography, broadening its scope enormously to complex multi-party transactions, and providing fundamental new methods for implementing such transactions.
TCS is inherently a highly mathematical discipline. Its basic philosophy and methodology -- formulating and analyzing precise models of computational systems that abstract key aspects of their behavior -- has been fundamentally influenced by the methodology of applied mathematics. TCS draws most heavily on discrete mathematics, probability, and logic, but it has growing connections throughout mathematics. The field of TCS initially grew out of logic and the basic notions of computability and complexity. Discrete mathematics soon became a central tool in the design and analysis of algorithms, as well as in the formulation and analysis of general computational models. Probabilistic methods have become increasingly important both to algorithm design, where randomized algorithms and probabilistic analysis have become essential tools, and complexity theory, where the probablistic viewpoint is fundamental to our understanding of computational models.
Computational geometry has become a major subfield of TCS, drawing heavily on both discrete mathematics and classical geometry. Number theory has played a key role in the design of cryptographic protocols. Computational algebra, algebraic topology, Fourier analysis, and geometry play an increasingly important role in proving lower bounds on computational complexity, as well as in the design of algorithms. Coding theory, long influenced by deep mathematical methods, particularly from algebra and algebraic geometry, presents methods for the robust representation of information and has combined with methods of computational information theory to achieve codes that are close to theoretical limits. The role of these and other areas of mathematics in the development of computer and information science, and in particular in theoretical computer science, is the major theme of this special focus.
At the same time that TCS is increasingly influenced by the methods and results of mathematics, the algorithmic methods of TCS are increasingly important in the analysis of fundamental problems of mathematics. For example, the discovery of algorithms that permit the rapid processing of vectors, polynomials, matrices, and other central mathematical concepts can be a tool in the solution of important mathematical questions. Exploring this direction of the connection between mathematics and TCS is a second theme of this special focus.
Opportunities to Participate: The Special Focus will include:
Index of Special Focus on Mathematics and the Foundations of Computer and Information Science
DIMACS Homepage