Let’s Have a Meeting
How things get invented
John Hopcroft is one of the great researchers who helped shape much of the foundations of the theory of computation. Some of this he did through his research, some through his great graduate students, some through his early textbooks. He did seminal work on algorithms and on basic complexity theory, leading to a well deserved Turing Award in 1986, joint with Bob Tarjan.
Today I want to talk about a much different kind of result. No theorems were proved—sounds like “no animals were harmed during the filming of this picture.” This work was joint with me, but it was never published. Actually, it was not possible to publish the work—yet it has a real impact on the community.
John’s work on algorithms included the start of the modern approach to graph isomorphism—joint with his then Ph.D. student Merrick Furst and Eugene Luks—and some of his work on complexity theory is still the best known. For example, with Wolfgang Paul and Leslie Valiant, he proved,
Theorem: For any ,
This is proved using the famous pebbling argument. If you do not know this result, it is a beautiful proof—take a look, since it is still the best result known about time and space.
Hopcroft has not only proved great results, he has a sweeping vision of the field of computing, a vision that he shared with his students and others. One of his ideas—it is not an exact quote—is:
Work on important problems. They may be as hard as other problems, but if you solve them, then you would have made a real contribution.
This explains why he worked on such hard problems as graph isomorphism, while others stayed away. If you are going to work hard and perhaps solve a difficult problem, then make it an important problem. I like this idea—although I have violated it plenty of times and worked on hard problems that few cared about. I do agree with John: work on important problems. I wish I had listened more to him. Oh well.
A National Meeting?
John and I created the notion of “Federated Conferences”; we did this back many years ago. Here is the story of how it happened.
I was on an advisory board for NSF chaired by Rich DeMillo in the early 1990’s. John was a member of the board. During one of our meetings John asked for a chance to explain what he thought was a national need of the computer science community.
John pointed out that all the other sciences had large national meetings. This included: biology, chemistry, mathematics, physics, and all the rest. Only computer science seemed to have no national meetings. He listed many of the advantages such a meeting would have:
- Bringing all the various parts of computer science together, it would help make the field more of a real community.
- Being large, it would help create excitement.
- Being national, it might attract national level press coverage.
He added other advantages of such a meeting.
As you would imagine there was lots of discussion, with lots of push back. Computer science had already had national meetings, most of them were weak and not attended by the top researchers. The top people in each area went to their respective top meetings:
- database researchers SIGMOD.
- programming language researchers POPL.
- system researchers SIGOPS.
- theory researchers STOC.
The last thing we needed, most argued, was another meeting; there were already too many meetings. Even worse, the last thing we needed was another weak meeting. The central question put to John was: Why would a theorist send a top paper to this new national meeting, when they could send it to FOCS/STOC and get more “credit?” Indeed why. John agreed with all these issues, but repeated his position: we needed a national meeting to be on par with the other classic sciences.
I listened and suddenly had an idea on how to solve John’s problem. I said what if we created a new meeting made up of the old meetings. The point was to simply have existing conferences meet at the same time and at the same place. Just co-locate in time and space.
This caused lots of discussion. Most liked the idea, and as a group we refined it quickly. Each conference would keep its current rules of how to accept papers; how long the talks were; whether the meetings where parallel or not; whether they had keynotes or not—they would not change anything. The only would give up control when and where the meeting where held.
I hope its okay to point out this story. Most—almost all—of you probably have no idea where the federated meetings came from, and most probably do not care. I wanted to make a point about problem solving. Problems come in all flavors and from all places, we should be flexible and be prepared to think out of the box.
See you at the upcoming federated meeting in 2011 at San Jose. I am proud to be part of this creation of the federated meetings. I do wish John and I got a nickel for each person who attends the meetings. Oh well.
The main open problem is: do these federated meetings really help? Do they really get people to talk, who might otherwise not see each other? What do you think?