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:

**Workshops:**A variety of workshops and mini-workshops are being planned.**Visitor Programs:**Applications for research and graduate student visits to the center are invited. Some funds are available for travel and local support.**Postdoctoral Positions:**We anticipate that several postdoctoral positions will be offered in this area.**Publications:**We anticipate that a variety of publications, including AMS-DIMACS volumes, technical reports, abstracts and notes on the WWW, and DIMACS modules will result from the special focus.

Index of Special Focus on Mathematics and the Foundations of Computer and Information Science

DIMACS Homepage

Contacting the Center

Document last modified on September 21, 2000.