Monday, March 28, 2005

Open Problems

John Langford points us to the COLT 2005 open problems CFP. The COLT open problems appear in the proceedings, a feature that distinguishes them from (for example) the SoCG open problems sessions, which are more informal.

It's worth pointing out that there are open problems, and there are open problems. Anyone who writes a paper can come up with open problems; these are merely the questions you didn't get time to address, and are either too bored or too unmotivated to work on yourself. These are not really that interesting. Good open problems are not necessarily easy, and are not too hard either (P?=NP is an open problem in the true sense of the word, but is not particularly useful as a proposal for this kind of forum).

A good open problem thus has some intrigue, has some surprise, and should tantalize the reader; the solution should appear to be just over the horizon, rather than indistinctly fading away. Any thoughts on good candidates ?

1 comment:

  1. I don't know if this is a good open problem. I might not be good. It might not be open. But it has vexed me.

    Ever since I've read about the Kobe embedding theorem, I always wondered what 3-d "coin graphs" would look like. By coin, I mean a flat 2-d disk living in R^3. Two disks are adjacent if their boundaries share a common point. Two disks cannot meet anywhere but on their boundaries. Given a graph G, can you find a realization of G using coins in R^3? If not, which ones are possible?

    I know this statement isn't rigorous but I hope you get the idea.


    Posted by Anonymous


Disqus for The Geomblog