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 strategic goals.)

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 (G7).

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 salient examples.

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 biology.

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 distributed enterprise.

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.

Contacting the Center
Last modified August 7, 1998