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 ${s(n) \ge n}$,

$\displaystyle \mathsf{DTIME}(s(n)) \subseteq \mathsf{DSPACE}(s(n)/\log s(n) ).$

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.

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 ${\rightarrow}$ SIGMOD.
• programming language researchers ${\rightarrow}$ POPL.
• system researchers ${\rightarrow}$ SIGOPS.
• theory researchers ${\rightarrow}$ STOC.
• ${\dots}$

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.

Federated Conferences

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.

The meeting ended and we eventually handed the idea off to CRA. They followed through and made it happen and that is how we got federated meetings.

Open Problems

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?

[fixed typo]

1. May 23, 2010 7:50 pm

Nice story — it’s always nice to be reminded to think creatively.

Also, according to your link, the federated meetings are in San Jose next year, not San Diego. Too bad!

May 23, 2010 7:55 pm

Andy,

Oops. Thanks for pointing this out.

May 23, 2010 10:11 pm

do these federated meetings really help?

To quote my home research community: Oh hell no.

SOCG was part of FCRC at the beginning in 1993. Community opinion was almost unanimous that the federated conferences were a ripoff—too expensive, in poor location, with none of the touted community-building—and we left FCRC after 1996. We were convinced to rejoin again in 2004 with the promise of rational registration fees—if you register for day X, you can attend any talk at any FCRC conference on day X. The FCRC organization swore up and down that this would be the policy, until about six months before FCRC, when they decided to go back to the register-for-each-conference model (which is the right model from a business standpoint, but utterly screws the purpose of having a joint meeting).

The computational geometry community then unanimously responded, “Fine, screw you and the horse you rode in on,” and never looked back.

May 24, 2010 12:55 am

It did come also on one of Michael’s posts recently. The registration fees for CS conferences seems to be too high, compared to sat math. I don’t really understand this. If people want to go to nice places to enjoy themselves, sure, there are other conferences held in nice and expensive places, but top tier conferences should remain cheap enough that students and post docs can attend. This problem should be addressed. In place of subsidizing students and post docs, the fees should drop to reasonable range. I would like to hear about why math conferences are way cheaper than CS conferences.

It also seems to me that CS is grown too big to have a common conference. When people in theory don’t go to the talks in FOCS and STOCS not related to their areas, I would not expect them to go to talks in say systems.

It might help if there is a separate day for having a limited number selective invited of talks that everyone in any of conferences can attend by registering in any of the conferences.

4. May 24, 2010 2:14 am

Although I’m sympathetic to the idea, I can’t see myself going because neither (a) is there a graphics related conference present nor (b) are there any apparent cross-area events going on. I think the concept of federated cs conferences is still substantially different than a math, physics or bio conference. As I understand it, those are primarily social and community affairs filled with unrefereed talks.

Maybe you could say something about how the federated conferences function in practice. I don’t really get a sense of how the colocation actually makes a difference.

May 24, 2010 9:41 am

I think several things seem to happen. One people in the “halls” see people they never would have before. Second, you can hear talks from other areas that you would otherwise have not heard. Third, they try to get keynotes that all can enjoy.

May 24, 2010 11:16 pm

As someone organizing a conference which considered FCRC, let me say a few things
a) Sorry if we were poor at communicating; we are a slow-moving group.
b) The FCRC became less attractive the more we learned.
c) I wish I could be there.

At first it sounded pretty good. Co-locate, let people pick and choose sessions, mega-fun. There were questions of community dilution; but that can become community expansion. The other conferences did have a somewhat tenuous connection to our community, though.

The real killer was the FCRC’s joint plenary sessions and other perceived interference with our schedule, ruining the experience for hard-core members of the community (e.g. some people hate “new” method X or buzzword Y or …). This would not have sat well. Also, 200+ people attend our independent conferences; many question the value of getting too big.

Today, we are nearing agreement to co-locate with OOPSLA/SPLASH (splashcon.org) instead. They are promising to organize the local arrangements and let us have a truly independent program.

Even still, some people strongly believe that this co-location will be bad for us.

May 25, 2010 1:08 am

I forgot to thank John Hopcroft and you for what you have been doing for the community in the above comment, including this great blog. Thanks.

May 25, 2010 10:49 pm

anonymous asked ” I would like to hear about why math conferences are way cheaper than CS conferences.”

I hear the philosophy conferences are even cheaper ;-)

“University President: Why is it that you [computer scientists] always require so much expensive equipment? Now the Department of Mathematics requires nothing but money for paper, pencils, and erasers…and the Department of Philosophy is better still. It doesn’t even ask for erasers.” – Isaac Asimov

May 26, 2010 2:05 am

Nice quote. I like Asimov.

Unfortunately I don’t see what equipments we are using in our **conferences** that mathematicians do not. (OK, maybe they prefer blackboards to slides, but that wouldn’t count for the difference.) This needs a more serious answer, not a quote.

Lets see some numbers. Lets compare STOC: http://research.microsoft.com/en-us/um/newengland/events/stoc2010/registration.htm

ACM/SIGACT/IEEE Member $500$600
Non-Member $600$700
Student $260$350

with for example: http://www.maa.org/mathfest/

Member $250.00 Non-Member$ 375.00
Grad Student $50.00 MAA Undergrad Student$ 50.00
Unemployed $60.00 Developing Country$ 60.00
K-12 Teacher $60.00 Emeritus Member$ 60.00
Single Day Friday $110.00 Single Day Saturday$ 110.00
Single Day Thursday $110.00 Short Course Only Non-Member$ 200.00
Short Course Only Member $150.00 Short Course Only Student$ 75.00
High School Student $25.00 PME Undergrad Student$ 50.00
New Member (includes One-Year Membership w/MAA) $290.00 Do you wish to register a guest (non mathematician) for the meeting for just an additional$25 fee?

Another example: http://www.cie2010.uac.pt/contents/registration.html

Registration Regular Student
Early 160 EUR 80 EUR
Late 220 EUR 130 EUR

Note that 160 EUR is right now less than 200 USD according to Yahoo.