Friday, August 20, 2004

"Conclusions and Open Problems" (by Adam Klivans)

Unless Lance has been involved in some unfortunate roller coster accident, this is most likely my last post. It remains to be seen whether I will be allowed to keep my posting privileges here on the board (place your bets on "No"). What I've taken away from this experience, more than anything else, is that posting every day is a tremendous time sink. Lance, kudos to you for the almost daily missive.

At the end of most technical talks is the obligatory "Conclusions and Open Problems" slide, usually the least thought out moment of the presentation, which consists of a brief summary of the talk and a list of the most obvious (difficult) open problems. For the last few years, COLT has glorified the open problems section and allocates about an hour of time for a presentation of open problems. The open problems themselves must be submitted months beforehand and are refereed (how rigorously is anyone's guess); accepted problems appear in the proceedings. A list of this year's open problems can be found on the COLT 2004 program schedule -- the session was held on Friday evening.

Are there any other computer science conferences where open problems are refereed and given their own slot in the program? It always seems to work out well at COLT, and while I am aware of open problems being presented at rump sessions at various conferences, I don't know of other venues which require advance submission of problems.

With that, gentle reader, I return you to Lance's wise embrace. If I ever get to guest blog again, I will reveal what's hidden in Lance's "Private" directory here on Some "lost" theorems apparently-- here's an aborted post entitled "Soon I will be famous: a simple proof that NP = coNP" -- and here's another unfinished note with some not so nice things to say about Algorithms. And what's this? A love letter to Jessica Simpson? Oh if only we had more time.


  1. Open problem sessions are a fantastic idea; I wish more conferences had them! Can you say a bit more about how the COLT session evolved?

    CCCG (the Canadian Conference on Computational Geometry) has an open problem session every year. The problems aren't refereed in advance, but thanks to Erik Demaine and Joe O'Rourke, they are published in Joe's "Computational Geometry Column" in SIGACT News and in the following year's proceedings (often with status updates). Here are the problems from 2003, 2002, 2001, 2000, and 1999.

    I think SoCG (the ACM Symposium on Computational Geometry) has had an open problem session once or twice, but it isn't a regular thing, in part because the number of submissions has gone way up recently. There's just too much community pressure to keep the schedule full, but short. 'Tis sad.

    For many years the call for papers for SODA (the ACM-SIAM Symposium on Discrete Algorithms) inlcuded "open problems" as an acceptable topic for (yecch) short papers. But as far as I know, only one open-problem paper was ever submitted, and (sniff) it was rejected.

  2. As it turns out, this year's Fall Workshop on Computational Geometry will have a special session on Open Problems.

    An excerpt:
    To promote a free exchange of questions and research challenges, there will be a special focus on Open Problems, with a presentation on The Open Problems Project, as well as an Open Problem Session to present new open problems. Submissions are strongly encouraged to include stand-alone open problems, which will be collected into a separate webpage and considered for inclusion in The Open Problems Project.

  3. This from Sanjoy Dasgupta on the origins of the COLT open problems session:

    "It officially started just two years ago (COLT 2002) but I think Manfred Warmuth and Yoav Freund had been toying with the idea for a while. A few years earlier, Yoav offered money to anyone who could solve a problem about switching experts. Olivier Bousquet (with Manfred) cracked the problem and the prize was given at COLT 2001 (I think), to much general amusement. That's when they decided to formalize the practice."