To: Fred Roberts
From: Tom Leighton and Christos Papadimitriou (chair)
Date: Thu, 6 Mar 1997
Subject: DIMACS Research Evaluation
Our two-member research evaluation team was given seven specific questions
(below) relating to the strategic and tactical
research goals of DIMACS, and the degree to which they are
being attained. We studied DIMACS' document on
strategic plan and evaluation standards,
the report of the October 1996 NSF site visit team, and
reports from several special years. We requested and promptly received
a self-study by the DIMACS management addressing the same seven questions,
as well as lists of DIMACS publications and past and present post docs.
Question 1: DIMACS has recently developed a statement of
purpose and specific goals for itself. The purpose and goals are
closely related to high quality research. What is your view of the
purpose and goal of DIMACS? Should they be different? Narrower?
Broader? How would you prioritize them?
The committee felt that the statement of purpose itemized P1--P5 and
the goals G1--G17 are fine. We did not identify anything that is redundant,
and could not think of any important omissions. However, we did feel that
the flat list of seventeen goals, in which major strategic issues coexist
with tactical subgoals, is unwieldy and possibly misleading. We believe
that a more structured exposition of the goals of DIMACS would facilitate
the required prioritization.
In our view, DIMACS has these two strategic goals:
S1: To promote high quality research in dm/tcs (this is G1).
S2: To have a long-term impact on dm/tcs, mathematics, science,
and society (G8).
(Although we are presently answering a question pertaining to the
goals of DIMACS, and not its success in achieving them, we should
nevertheless mention here that, in our opinion,
DIMACS is doing superbly with respect to both of its
To achieve strategic goal S1 DIMACS must choose appropriate areas of
research emphasis (G2), facilitate interactions and collaborations (G4), and
involve outstanding young researchers (G6); we see these as equally important
subgoals of S1.
To achieve long-term impact (strategic goal S2), DIMACS must choose
research directions with expected high impact on Computer Science
primarily, secondarily on key subfields of the physical and applied
sciences, and on the rest of Mathematics (G2, G9, G10, G13). It must
involve and train bright young researchers and students (G6, G11), and
it must disseminate its results and knowledge effectively to other
areas, to industry (G5) and to society and the next generation through
education (G12, G14). It must also be recognized nationally and
internationally as a singularly important and indispensible resource
The nature of DIMACS, its strategic goals,
the funding situation and political realities
surrounding it, as well as its size
and complexity, necessitate three important tactical goals,
which we discuss more substantively below:
T1 DIMACS must take advantage of the center mode of operation (G3),
and, in fact, it must do so in a manner that is
convincing and demonstrable .
DIMACS chose a unique variant of the center mode, which can be called
big-scale small science. Research effort is fragmented both
across subareas of dm/tcs, and along the time axis (special years etc.).
Nonlinearity of return is achieved through the unity of the field, and its
strategic position within Computer Science, Mathematics, and the
natural and applied sciences.
This variant of the center mode is very appropriate for dm/tcs, but makes
tactical goal T1 much more subtle.
T2 DIMACS must be managed competently, meticulously,
flexibly, and creatively (G17). DIMACS' well-known difficulties in
this area were, until not so long ago, arguably the only dark spot in
a very bright picture, and seriously threatened the center's future.
Big strides in this arena have been made more recently, and this
aspect is at present, in our opinion, completely satisfactory.
T3 DIMACS must obtain research support from outside NSF's STC
program, including increased support from its member institutions
(G15--G16). In our opinion, the obtained increased support must reach
a level that guarantees DIMACS' continued effective operation beyong
year 11. There is a complex game-theoretic situation here: If DIMACS
is too successful in raising internal and outside funds, it would
appear that NSF may be less motivated to continue its STC support
beyond year 11. In the committee's opinion, this is not a
consideration that should interfere with DIMACS' determination to
obtain increased institutional support, as well as more outside
research funds. Incidentally, obtaining more outside research funds
may necessitate longer-term and more focused research projects than
the special years, and the committee is applauding DIMACS's decision
to move in this direction.
Question 2: One of DIMACS' purposes is to promote and
support high quality research within the fields of dm/tcs, especially
research areas that are ``poised for rapid development and have potential
for high impact.'' Is this purpose being achieved?
In our opinion, DIMACS has succeeded spectacularly in promoting high-quality
research in dm/tcs, and in choosing fruitful and strategic research
foci; this is documented very well in Section 2.2
of the self-study. We would like to add these observations:
First, most celebrated breakthroughs in the past seven years in
dm/tcs have had a strong DIMACS component, and were arguably
catalysed by DIMACS; the research that resulted in the PCP
characterization of NP, the quantum-mechanical algorithm for factoring,
and the recent polynomial-time approximation
scheme for the euclidean traveling salesman problem are three of the most
It is also worth noting that certain important and highly beneficial
trends in dm/tcs were accelerated at DIMACS:
Experimental analysis of algorithms, verification technology, computational
The DIMACS model of year-long focused emphasis on selected subareas
often helped redirect research talent in an area of dm/tcs
towards more novel and productive directions within the same area:
Designers of efficient algorithms started using experimental
methodology, researchers working on abstract computational models of
biological systems saw the true problems facing computational biology,
and researchers in logic became aware of the challenges of
verification, testing, and hybrid systems.
FOCS and STOC are two prestigious and exclusive international
annual conferences in dm/tcs,
broadly considered as the premier publication venues of the
field. DIMACS' presence in this exclusive forum
has been extremely strong: Since 1989, almost a third of the
papers presented in FOCS and STOC have had a DIMACS connection,
authored or co-authored by one or more DIMACS permanent members, or by a
DIMACS post doc.
It would be interesting to determine how this compares with the
sum of the presence of the DIMACS institutions in the years before 1989.
In the 1988 FOCS, the last such conference
before the start of DIMACS, the proportion of papers co-authored by
would-be DIMACS members was less than one-sixth.
Question 3: Two other DIMACS purposes are to promote
and support application of the methods and results of dm/tcs in other
areas of science, the mathematical sciences, and industry; and to
encourage and facilitate the efforts of researchers in these fields to
draw more of their research inspiration from other areas of science, the
mathematical sciences and industry. Are these purposes being achieved?
We are less eager than DIMACS' management to carefully distinguish
between these two purposes. Applications of dm/tcs are rarely
unanticipated and accidental, they are usually the result of conscious and
purposeful choice of research direction. The best way to draw inspiration
from an applied field is to have some direct or indirect involvement with it.
We believe that DIMACS has an excellent record of steering its
research priorities towards directions that at the time promised (and
in retrospect turned out) to have high impact and direct application
to key areas of Computer Science, and the natural and mathematical
sciences; this is documented well in the self study. Furthermore, the
industrial members of DIMACS are eager to directly involve their
dm/tcs researchers in the applications of their ideas and results.
The recent emphasis on collaboration between theoretical and applied
researchers in the workshops is a particularly effective way to
achieve applications-oriented goals. As attendees at some of the
recent workshops on network protocols and algorithms, we have been
particularly impressed with the level of interaction between theorists
and practitioners. This sort of interaction tends to come about only
as the result of careful planning and is another way in which DIMACS
is unique in dm/tcs. Indeed, these meetings are so valuable that we
routinely send our students to attend DIMACS workshops with
the express goal of learning what the applied problems are and who is
working on them.
Question 4: One of DIMACS' goals is to facilitate
interactions and collaborations within dm/tcs by making it easier for
researchers both locally and from all over the country (and the world)
to interact, thus facilitating rapid development of an area, and by
connecting researchers in dm/tcs in different communities or withing
differing areas of emphasis. Is this goal being achieved?
The self-study documents many instances of fruitful and lasting
collaborations between dm/tcs researchers that began within the
framework of special years. We add that, in our opinion, the DIMACS
special year themes, and the lists of invited participants, were
well-chosen for facilitating such collaborations. The self-study also
identifies several ways in which interaction could be improved (for
example, during the periods of lull between special year meetings).
Question 5: One of DIMACS' goals is to involve outstanding
young researchers in all DIMACS programs, so as to maximize the long-term
impact of these programs. Is this goal being achieved?
This DIMACS goal has been achieved mainly through the DIMACS post
doctoral program, one of the most imortant activities of DIMACS. This
program, supported by DIMACS funds and leveraged by the DIMACS
industrial partners, has involved in DIMACS life and research about
ten of the brightest young researchers in dm/tcs each year. The
postdoctoral career stage is a 90s novelty for the dm/tcs community,
brought about by the relatively low supply of academic positions in
the past ten years (there is currently a new surge in this supply,
which could cut in the demand for DIMACS post docs). Approximately
half of all post doctoral positions in the country were at DIMACS.
The DIMACS post doctoral program has therefore been very helpful for
both DIMACS' strategic goals, and the community.
Post docs in dm/tcs are typically of one year duration, perhaps reflecting the
situation in the job market, and the amount of buffering it
necessitates. DIMACS wants to extend this to two years;
this should be done only if the quality of the researchers
involved can be preserved at the same level.
Looking at the 48 past DIMACS post docs and their career paths after
DIMACS, almost 80% are at academic positions, some 10% are at
industrial positions, and the rest are doing further post docs. One
statistic that may attract NSF's attention is that one third
of them are following academic careers in other countries. This seems
rather natural and in line with our experience with dm/tcs in general,
it is consistent with DIMACS' international mission of leadership, it
is hard to avoid and prevent, and may also reflect the difficulties in
the U.S. job market during that period.
Question 6: DIMACS would like to be a vibrant national
resource for the dm/tcs community. Is it such a resource now?
If not, what kinds of changes should DIMACS make to ensure that the
community think of it in these terms?
In our experience, the dm/tcs community does consider DIMACS to be
an important and valuable national resource. We do not believe that
many researchers in dm/tcs see DIMACS as a regional, New Jersey-focused
enterprise. Special year invitees come to DIMACS from all over the
country and the world, and DIMACS post docs originate from all over
the country and the world, and end up likewise. Results obtained at DIMACS
dominate the prestigious annual dm/tcs conferences. The scope and radiance
of DIMACS is definitely national and international.
The DIMACS management is apparently concerned about the perception of
DIMACS by the overall Mathematics community. Although its support
would be most valuable, this community is too extensive, diverse, and
with too many preconceptions regarding dm/tcs, for DIMACS to hope to
have it solidly behind it. True, the late founding director's status
within the Mathematics community was a valuable asset in this regard,
which DIMACS is unlikely to replace in the near future. The sessions
and other activities organized by DIMACS in the national fora for
Mathematics should help a little.
Question 7: What would move you, if you were reviewers,
to argue for significant support for the center? (Related question:
DIMACS involves many powerful institutions, which would have had significant
research productivity in dm/tcs, DIMACS or not. How can you document
the impact of DIMACS?)
This is the crux of the matter, how to document the success and
continued necessity of the center mode of support within the context of
the ``large-scale small science'' practiced at DIMACS.
Necessarily, the answer lies in the specific nature of dm/tcs and
of the DIMACS partners.
The field of dm/tcs has attracted much talent, and has a vast potential of
influencing Computer Science, the computing industry, as well as other realms
of science and industry. One of its defining characteristics is
the speed with which research topics and application-driven
subareas become important or fall from relevance. In the past seven
years DIMACS, advised by some of the most respected senior leaders in
dm/tcs, has provided much needed leadership and guidance to the field,
steering a substantial part of it towards research directions and subareas
chosen with wisdom and insight. This aspect of the function of DIMACS
is something that certainly could not be replaced by a smaller-scale and more
DIMACS' industrial partners comprise between them a very substantial
part of industrial dm/tcs. Basic industrial research, including industrial
research in dm/tcs, underwent a major transformation during these past ten
years nationally, especially with respect to corporate expectations
regarding its internal short-term utility. In many industrial research
centers morale has been low, and attrition high. The dm/tcs sectors of
DIMACS' industrial partners have weathered this crisis better
than most places; this can be attributed partly to the
existence of DIMACS.
DIMACS' industrial partners have a special interest and commitment in
dm/tcs, and DIMACS has served them very well.
We believe that nothing would be more convincing evidence of
DIMACS' success as a center that is valuable to both the dm/tcs community
and its partners than a substantial increase of the industrial
partners' contributions, and their tangible
commitment to support DIMACS beyond year 11.
Finally, anecdotal evidence of successful and continuing
collaborations that started at DIMACS, cross-fertilizations that took place
there, big results that were catalysed by sustained focus on a subarea, and
testimony by researchers on the value of the center mode, certainly
help this argument. The self-study (and not only Section
2.7) contains many such anecdotes, and we
are sure that many more can be compiled. Also, DIMACS' presence in
FOCS/STOC, briefly discussed elsewhere in this report, is
a measurable quantity that could perhaps be used.
DIMACS home page
Contacting the Center
Last modified August 7, 1998