Evaluation of the DIMACS Special Year on Logic and Algorithms

Neil Immerman (chair) and Tom Henzinger

October 1, 1996

(Note: The two of us agreed to do this evaluation even though we were each involved with parts of the special year: Immerman was a teacher in one of the short courses, a co-organizer of the Descriptive Complexity Workshop, gave one of the distinguished lectures and was a visitor for several weeks in the Fall of 1996; Henzinger was a co-organizer of the Hybrid Systems workshop, participated in the Workshop on Controllers, and co-organized CAV96, part of the Federated Logic Conference.

During the 1995 - 1996 academic year, DIMACS sponsored a special year in logic and algorithms. The total expenditures for the special year from all sources was about $390,000, of which $250,000 was the DIMACS special year budget.

The special year included eleven workshops, a seminar series, a distinguished lecture series, three weeks of tutorials, support for many short-term visitors and several postdocs, and the Federated Logic Conference - FLOC'96. In the following we describe what we feel were the strengths of the special year, we mention a few weaknesses, we consider the industrial contacts, and finally we make a few suggestions for future special years.

In order to do this evaluation, we talked with colleagues, used information provided by DIMACS, and we conducted an email survey of participants in which we received 65 responses.


The greatest strengths of the special year were the tutorials and workshops. The tutorials offered three weeks where graduate students, postdocs, and others could become familiar with the areas of a special year, learning the material from some of the leading researchers in the area. Many people commented that these tutorials enabled them to quickly become familiar with the ideas and issues in a new research area. The tutorials engendered new research, collaborations, and also some thesis topics. Some of the postdocs said that the tutorials were the most valuable aspect of the special year in that they enabled these young researchers to quickly begin research in new fields with their new colleagues.

The large number of excellent workshops that were held as part of the Special Year in Logic and Algorithms reached the greatest number of people and had a substantial, positive effect. The key features were excellent talks, excellent participants and the opportunity to interact with many of the experts in the areas of the workshop in a relaxed setting.

Most people reported extremely positive experiences at the workshops. Many research papers and projects resulted from the ideas and interactions at these workshops. In one such example, at the Random Structures workshop, Monica McArthur, Joel Spencer, and Saharon Shelah worked out an extension of Zero One Laws to stronger logics than had been previously known. In another example, a talk by John Franco at the Satisfiability Workshop, and a question by Alan Van Gelder, have led to a collaboration between the two that has identified what seems to be a significantly larger class of `easily solved' formulas than had been previously known. There are many other examples of new research, new and now on-going collaborations, postdocs matched with senior scientists, graduate students finding directions for their research, etc.

A special feature of these workshops is that a high percentage of the active researchers in the various topics of the special year were able to come to at least one workshop. The quality of the people participating in the workshops and the efficiency of the DIMACS staff fostered a very high opinion of DIMACS throughout the world.

Here are a few specific comments, condensed and summarized from many made about the workshops:

The DIMACS staff should be congratulated for the smooth running of all of these workshops. Almost everyone commented that they were well run. There were no logistical problems and thus the scientific interactions were facilitated.

Another strength of the special year were the excellent postdocs and visitors. Again, collaborations were started. One particularly beneficial example was between the year-long postdocs Etessami and Wilke who have established an active collaboration combining the methods of finite model theory and temporal logic. Many of the short-term visitors commented on how fruitful their stays were and mentioned research and collaborations that resulted.

Industrial Contact

There is substantial industrial interest in work relating to computer-aided verification. The following five workshops related to this area had participation by members of industry:

In addition, CAV96 - the Computer-Aided Verification Conference that was part of the Federated Logic Conference - included one morning devoted to invited speakers from industry. These talks, which were extremely well-received, gave a high-level, managerial perspective on trends in industrial verification. By contrast, low-level, technical talks by industrial developers are often not very exciting for the research community.

Many people commented that the interactions with industry were valuable, important, and useful. People also lamented that for the most part the industrial interaction was limited. (Here we are not talking about industrial research labs - there was substantial participation in the special year by members of such research labs, Bob Kurshan being a notable example.)

Several people cited the Workshop on Controllers for Manufacturing and Automation as having made a very good attempt at establishing a dialog between industrial developers and academic researchers, but said that this task is very hard to accomplish because of the quite different points of view. More needs to be done in this direction.

A quote from one of the participants in the Controllers for Manufacturing Workshop underscores the difficulties, ``Certainly, attempting to bring industry researchers and academicians [together] is useful. Some of the industry talks that I heard, on the other hand, were extremely boring and were not useful at all.''


The main weakness that we can point to in this very successful year is that there was an insufficient core group of researchers based at DIMACS. There was a lack of critical mass. There was also a lack of senior, long-term visitors to make DIMACS be the place to be - even at times when no workshops were going on - for researchers in fields related to the special year.

A number of people commented that they were not really aware of the special year except for the usually single workshop that they attended. If there had been a few more postdocs and one or two senior sabbatical visitors, there could have been a sustained critical mass with a larger seminar series, regular teas, and a real center of activity. Teas, in particular, would have the advantage of drawing the Rutgers faculty over to DIMACS for more frequent interaction. In this case, some of the other activities, such as the distinguished lecture series, would have had greater impact. (The one or two senior visitors can be funded at the expense of some of the many short-term and mostly junior visitors DIMACS hosted over the year.)

Associated with this, some people complained about the lodgings. The main concern is that some participants in tutorials and workshops went back to their hotels in the early evening and were isolated from the other participants. This is in contrast to workshops that occur at a hotel, or even better at an isolated and attractive research center like Oberwolfach or Dagstuhl. DIMACS should recognize this problem and make a greater effort to have more frequent catered dinners at the center and other social activities to keep the participants in contact with each other through the evenings. (There were also apparently some serious problems with two of the hotels that had been but are no longer on DIMACS' recommended list.)

Suggestions for the Future

We feel that this was a highly successful special year. Its greatest impact is that it brought a very large number of active researchers in contact with each other, thus making connections, establishing contacts, and producing a substantial amount of new research and on-going collaborations.

We would make the following suggestions - along with those already made above - for future special years.

The tutorials were crucial and should be part of all future special years. These were a great boon to many researchers who were thus able to quickly become familiar with new and active research areas.

If there is enough of a core group present at DIMACS for the special year, then the tutorials will help the visitors learn what everyone else is doing and begin collaborations. Similarly, these will draw students and other researchers from many of the local universities and research labs to the center and encourage them to continue their interactions with the center throughout the special year. A model for this kind of core group, might be the larger groups of senior visitors who visit MSRI in Berkeley for special years.

In general, we feel that funds for visitors are much more effective when spent on long-term visitors - those who stay at least several months to a full year - rather than short-term visitors. We also believe that an extra effort is required to foster interactions between the DIMACS visitors and Rutgers faculty, and also between the DIMACS visitors and researchers at Princeton, Bell Labs, and Bellcore. Contact with at least some of these institutions is essential for a worthwhile visit to DIMACS.

The rich feast of workshops bringing in a wide range of visitors were the strongest feature this year and deserve great organizational effort and support. This success should be repeated in future years.

It would be very valuable for the organizers of future special years to work in advance for strong and sustained ties with industrial research and development. As we saw this year, time has to be taken to foster communication between these diverse groups.

A similarly difficult but worthwhile problem is how to encourage more minority participation. This again involves a great deal of outreach before the special year begins so that scholarships can be offered and promising minority students can learn about appropriate activities such as the tutorials early enough so they can come and benefit.

Another minor topic is the use of the World Wide Web. Here DIMACS has done a good job in using the Web to publicize activities of the special year and in keeping information current. Still more could be done so that a researcher anywhere in the world can easily check what is happening at DIMACS, when all the activities will be held, and who will be visiting when.

After workshops, tutorials and other activities are held, it would be useful to maintain an ongoing presence on the Web, with a forum for discussions, the posting of the final papers from the workshop, as well as pointers to other current and related research.

Publications of the Special Year on Logic and Algorithms

  • Bibliography of papers traceable to the Special Year on Logic and Algorithms.
    DIMACS home page
    Contacting the Center
    Document last modified on July 8, 1998.