Open problems
I am a fan of the culture of open problems, posing them, solving them, passing them around in parties to prod people into action. Two collections of open problems are interesting:
- Andrew McGregor has compiled a bunch of open problems on data stream algorithms, with background and bib notes. Excellent!
- Jiri Matousek has a fantastic tome of open problems on low distortion embeddings, recently revised to also show solved problems since the origins of this document in 2002.
posted by metoo at 4:45 PM
4 Comments:
The list of open problems on embeddings is really nice! It has been a great source of interesting questions.
Although it seems that it is being updated quite regularly, there are a few results that are not completely up to date. I wonder if it would be possible to organize a wiki with open problems. Has anyone done this before? Maybe even something that covers several different topics (not just metric embeddings)?
I found Matousek's collection is very useful in my research.
My problem with these kinds of collections, in general, is that they are public for everybody to edit/update and they are usually months behind the newest results.
As tasos suggested I think a web solution is needed.
We are actually working on such a service on http://academier.com
Ideally there would be a place were open problems are listed, known topics are surveyed (real-time with data generated from users) and every body can easily contribute.
I like the idea of a wiki, collectively edited and reedited, without a topdown control. In some parts of the world, it will be sufficient to say, "Make it so!"
A paper which gives a O(1) distortion for embedding graphs into spanning trees under l_q metric may also be pertinent to people working in this area.
http://www.cs.huji.ac.il/~neiman/tree33.pdf
Post a Comment
<< Home