A Decade at DIMACS
April 22, 1999
With DIMACS director Fred Roberts (left) at the center's tenth-anniversary meeting were Bell Labs associate vice president for research Alfred Aho, Mihalis Yannakakis, a member of the DIMACS executive committee, and featured speaker Moshe Vardi.
DIMACS, the Center for Discrete Mathematics and Theoretical Computer Science, is 1010 years old.
That's base 2, of course. DIMACS recently celebrated its tenth anniversary, with a day-long program of talks and panel discussions at its Rutgers University headquarters. Talks sampled some of the research topics tackled at DIMACS over the last decade. The panel discussions considered the center's industrial and educational outreach programs.
Up and Running
DIMACS was founded in 1988 as a consortium of researchers from four institutions: Rutgers, Princeton University, AT&T Bell Laboratories, and Bellcore. It was one of the first 11 Science and Technology Centers funded by the National Science Foundation.
"We found out in December we were going to get the award, and NSF gave us the money in February [1989]," recalls DIMACS director Fred Roberts. "They gave us $10 million for five years, and we didn't even have a place to house this thing!"
The center opened shop in some trailers in a Rutgers parking lot. (It is now headquartered on the fourth floor of the CoRE Building at Rutgers.) The original director was the late Daniel Gorenstein, who in the 1970s organized the worldwide effort that culminated in the proof of the "enormous theorem" classifying finite simple groups. ("He was not a brilliant administrator," Felix Browder, a colleague of Gorenstein's at Rutgers, recalled in a lunchtime address, "but he was a brilliant leader. He knew how to get people to work together-even people who didn't like each other.")
DIMACS now has six institutional members: The NEC Research Institute came on board in 1998, and AT&T Bell Laboratories split into AT&T Labs-Research and Bell Labs, the research and development arm of Lucent Technologies, in 1996. Approximately 175 researchers at the six participating institutions are officially "permanent members" of DIMACS. The center also sponsors a dozen or more postdocs each year, with funding from various sources. (Some postdocs, for example, are shared with one of the institutional members or with the Institute for Advanced Study in Princeton.)
DIMACS was envisioned as a focal point for research in the mathematics and computer science that underlie modern information technology. For the first few years, the center's programs concentrated on "traditional" areas of theoretical computer science and discrete mathematics. Two early successes, achieved during the center's Special Year on Discrete and Computational Geometry, were the discovery of a linear-time algorithm for triangulating polygons---a key computational step in many geometric problems---and the solution of the famous Gilbert-Pollak conjecture concerning the relation between minimal Steiner trees and minimal spanning trees (see SIAM News, January 1991). The triangulation algorithm was discovered by Bernard Chazelle, a computer scientist at Princeton University who recently completed a term as co-director of DIMACS; the Steiner-point problem was solved by permanent member Frank Hwang and DIMACS postdoc Ding Zhu Du, both then at Bell Labs. (Du is currently at the University Minnesota; Hwang is at Chiaotung University in Taiwan.)
Several other important developments had roots in early DIMACS programs. In particular, the Special Year on Complexity Theory of Interactive Computation, 1990-91, saw a major breakthrough in theoretical computer science: the discovery of deep connections between interactive algorithms, which can be construed as proof-checkers, and the difficulty of finding approximate answers to classically "hard" computational problems, beginning with the maximum-clique problem for graphs (see SIAM News, May 1992). Numerous people, many of them DIMACS members or visitors, contributed to the web of theorems.
More recently, DIMACS has ventured into "nontraditional" areas of discrete mathematics and theoretical computer science. In 1994, the center initiated a Special Year on Mathematical Support for Molecular Biology, which has metamorphosed into a Special Half-Decade: The program is scheduled to run through 1999. Problems posed by biologists, ranging from the construction of phylogenetic trees to the paradoxical persistence of deleterious genes, have proved to be fertile ground for mathematical analysis and computation.
The 1995-96 Special Year on Logic and Algorithms brought together experts from two disparate branches of theoretical computer science: finite model theory and computational complexity. Researchers made inroads in the field of computer-aided verification, the seemingly impossible task of ensuring that programs do what they were intended to do. (Much of the work focused on nailing down just how NP- or PSPACE-hard various verification problems are.) Participants in the two-year Focus on Discrete Probability (1996-98, co-sponsored by the Institute for Advanced Study) explored topics ranging from the probabilistic method in discrete mathematics to the combinatorial and computational implications of statistical physics. Probability theory is becoming increasingly prominent in computer science, especially as networks of independent, unpredictable, and sometimes faulty computers grow to a size that a physicist would consider to be at the "thermodynamic limit."
The center is currently running programs on networks, massive data sets, DNA computing, and large-scale discrete optimization. (Joan Feigenbaum, a permanent member of DIMACS at AT&T Labs-Research, will give an invited presentation on massive graphs at the 1999 SIAM Annual Meeting in Atlanta, May 12-15; see article in this issue.) Scheduled for 1999-2000 is a Special Year on Computational Intractability.
"One of the things that DIMACS is about," Roberts explains, is trying "to get different people with different backgrounds talking to each other. It's one of the beauties of this 'center mode' of operation, that you can run larger and more complex programs, and you can do things that aren't traditional."
One of the things that DIMACS is about," said DIMACS director Fred Roberts at the center's birthday celebration, is getting "people with different backgrounds talking to each other."
Discrete Inquiries
Speakers at the DIMACS birthday bash touched on a few of the topics investigated by center researchers during the past decade. Richard Karp of the University of Washington surveyed some of the combinatorial optimization problems that have cropped up in the Human Genome Project. The goal of the project is to sequence the roughly three billion base pairs of the human genome with an error rate of less than one mistake per 10,000 base pairs. The goal would be easy to achieve if an entire strand of DNA could simply be grabbed and "read" from one end to the other. Unfortunately, current technology makes that possible only for strands about 500 base pairs long. Consequently, a key step in gene sequencing is the construction of a "clone library" consisting of short, overlapping fragments of a long "target" strand. Finding the best way to construct and utilize such clone libraries is a serious, and clearly important, mathematical challenge.
Ricky Pollack of New York University described some similar challenges in computational algebraic geometry. The mathematical description of a robot and its environment often boils down to a system of polynomial equations and inequalities in several variables, the implied solutions being real numbers constituting what's called a semi-algebraic set. (If the system involves no inequalities, the "semi" is dropped.) The first problem is purely existential: Given a system of equations and inequalities, is the corresponding semi-algebraic set nonempty? When the answer is yes, a second problem is to characterize the connected components of the semi-algebraic set and establish an algorithmic "roadmap" that will find a path connecting any two points in the same component.
Jennifer Chayes, a mathematician at Microsoft Research, talked about the crossover of ideas from statistical physics to problems in graph theory and related areas. Physicists have long worked with a notion they call finite-size scaling, which enables them to infer details of phase transitions from the behavior of large but finite models. The insights from statistical physics help clarify---and extend---theorems about the properties of random graphs.
Other speakers included Pavel Pevzner of the University of Southern California, on combinatorial problems of gene rearrangements (it turns out that what distinguishes human from mouse, or cabbage from turnip, is not so much the genes themselves as the order in which they appear in the genome); Moshe Vardi of Rice University, on new, model-theoretic approaches to the problem of verifying complex computer programs; and L�szl� Lov�sz of Yale University, on methods for speeding up sampling by Markov chains.
On hand to mark the occasion were Richard Karp, who gave a talk on combinatorial optimization problems arising in the Human Genome Project, Israel Gelfand, and Pavel Pevzner, who discussed combinatorial problems of gene rearrangement.
Industry and Education
Panelists in a discussion of academic/industrial cooperation stressed the value of basic research, but pointed out that the uncertain payoffs and the time scales involved limit industry's commitment to investments without a clear-cut, immediate return. "We can't afford to do only basic research," says Alfred Aho, associate vice president for research at Bell Labs. In recent years, he adds, "getting results quickly to the marketplace has become dominant," especially in computing and telecommunication.
C. William Gear, president of NEC Research, warns against building academic plans based on industry as a primary source of funding for academic research. The knowledge that comes out of academic research is welcome---DIMACS is "an incredibly valuable resource," he says---but most of that knowledge is not directly useful to most companies. Instead, Gear sees taxes and tax incentives as the best bet for funding basic research. "Ultimately, it's going to be a part of the cost of doing business."
Universities do produce one "product" that industry can't do without, Gear points out: graduates. "The most important role of the university is education," he says. DIMACS's educational role was the subject of a second panel discussion.
"Discrete mathematics is accessible to a broader audience than traditional mathematics," says DIMACS associate director for education Joseph Rosenstein. The center runs numerous educational programs at levels from kindergarten to collegiate. The Leadership Program in Discrete Mathematics, for example, is a two-week summer program for K-8 teachers. The DIMACS Research and Education Institute (DREI) is a three-week program during which high school teachers interact with researchers; the topic scheduled for 1999 is graph theory and its applications to problems of society.
DIMACS also hosts a Young Scholars Program in Discrete Mathematics aimed at high school students, an NSF-funded Research Experiences for Undergraduates (REU) program, and a Reconnect Program designed for faculty at two- and four-year colleges. Panelist Margaret (Midge) Cozzens, vice chancellor for academic affairs at the University of Colorado at Denver, considers DIMACS an "exemplary model of the 'vertical' integration of research and education," bringing together people at very different levels.
Do Not Go Gentle Into That Good Night . . .
DIMACS's run as an NSF Science and Technology Center is winding down. That's built into the STC program. "NSF originally expected that after 11 years, the Science and Technology Centers would be able to become self-sufficient, and so made these grants non-renewable," Roberts explains. DIMACS's STC status ends January 31, 2000.
Many of the STC's certainly will close down with the end of their NSF funding, Roberts observes. "DIMACS, however, is different. Rather than focus on the research of its local scientists, it views itself as a national resource and seeks to serve a national and international community." The center has support from several sources, especially its member institutions. Plans for the next special year, slated to run through August 2000, "are very far along," he says. In fact, the center is currently developing plans that will carry its programs to the year 2005. Among the topics for future special years are the next-generation Internet; the interface among computer science, coding, and information theory; the analysis of algorithms; data analysis and learning; and applications of algebraic geometry.
"We are looking for additional partner organizations and talking to various agencies and foundations about future support," Roberts says. "DIMACS is optimistic that it will have the resources to continue operating as a national resource in the years to come."
Maybe till it turns 1010 for real.
Barry A. Cipra is a mathematician and writer based in Northfield, Minnesota.
