A readers asks where he can put his open problem on the web. Back in the late 80's we had three Theorynet mailing lists. Theorynt-A announced major conferences, Theorynt-B announced local workshops and Theorynt-C had everything else including various questions people put out to the community. But now we have only one Theorynt only announcing conferences and the volume of a Theorynt-C type list today would overwhelm anyone trying to read it.
We need some Web 2.0 system. A blog or wiki to post the problems. A tagging method to mark the area and status. A voting system to rank the importance of the problem. A commenting system for discussion. A sophisticated RSS system for tracking. A visual appealing and simple interface. And most importantly someone willing to put it all together for no compensation beyond the thanks of the community.
I'm not sure I ever saw the point of these "open problem" lists. People in the area generally know the main open problems already. The really good open problems (i.e., those that are reasonably important yet likely to be solvable) people tend to not want to share. The only possible use would be for a grad student getting into an area, but wouldn't a knowledgable advisor be better than a wiki?
ReplyDeleteWhy doesn't Scott Aaronson volunteer to do the job? :-) After all he's a great zookeeper.
ReplyDeleteSome of us are not blessed with knowledgeable advisors, at least not in the very specific areas we would like to do research in.
ReplyDeletePossibly people can post these problems along with prize money(might be token or lot more than that) like Erdos used to do with his open problems. The prize money (and who it is offered by) would be a reflection of the importance of the problem. Possibly other people can add to the prize to make the problem lucrative and claim that the problem is quite important.
ReplyDeleteOpen problems lists can be of considerable benefit to a community. For example in computational geometry Joe O'Rourke began the Open Problems Project . (Joe is now joined by Erik Demaine and Joe Mitchell in maintaining the list.) Moreover, open problems are annually solicited for SOCG. It helps the community that problems from the list are regularly knocked off.
ReplyDeleteThere is no really good reason that we don't have similar lists for many areas in computational complexity. Unfortunately the CCC rump session serves multiple purposes (both announcements of results and of open problems) and is both too short and too broad to be effective for providing this for the field.
Smaller, more focused workshops can do this quite well. I have found motivation for some of my own work in open problem lists compiled at workshops on proof complexity and Boolean function complexity. Are there good lists for APPROX or RANDOM? They are sufficiently focused that they would be ideal for producing lists of open problems in their respective areas.
Anyone who doubts the value of open problems lists need only look to a certain 107-year old list of 23 problems...
While we're at it, how about some place to keep results that do not fit in the taxonomy of the zoo? I'm imagining a wikipedia-clone that is not geared towards being an encyclopedia.
ReplyDeleteChasing references back and forth through Google feels so 1998.
What's wrong with writing a good survey paper every now and then ?
ReplyDeleteDoes everything really needs to be Web 2.0 with tags and RSS feeds ?
I read survey papers, but they take time for authors to write up and can fall out of date quickly. They also reflect the opinion and taste of only a couple authors. I completely agree with Paul Beame about the value of open problems, and I'm sure I would benefit from such a site even with a very knowledgable supervisor. Such a site wouldn't immediately need all of the features Lance mentioned; it might be enough to start with a simple Wiki.
ReplyDeleteHere's one that I've found very vexing: Let A(d) denote the least surface area of a cell that tiles R^d via the translations in Z^d. Improve on the following bounds:
ReplyDeletesqrt(pi e / 2) sqrt(d) <= A(d)/2 <= d - exp(-Omega(d log d)).
(It's a little more natural to consider A(d)/2 than A(d).)
The lower bound is by considering a volume-1 sphere, the upper bound by monkeying around a little with a cube's corner.
Any proof of A(d)/2 >= 10sqrt(d) or A(d)/2 <= d/10 would be very interesting.
For motivation: Either pretend I posted on Suresh's blog (so it's just a problem in geometry); or -- it's related to finding the best rate for parallel repetition of a simple family of 2P1R games.
Here's a problem that's open for me (though I am sure the answer is known): given an unsorted list of n items x_1, ..., x_n, is it possible to determine in linear time whether there are distinct indices i, j with x_i = x_j (and, if so, also find i and j)?
ReplyDeleteWhy not just add the feature to complexity zoo? It might actually be better to do it this way.
ReplyDeleteAnon 11:
ReplyDeleteUse a hash table.
Anon 12: I am looking for an algorithm that is guaranteed to be correct, with worst-case linear running time.
ReplyDeleteWhat kind of items?
ReplyDeleteTo anon poster 11:
ReplyDeleteYou may be interested in looking at Theorem 5 (in page 655) of Ed Reingold's paper, On the optimality of Set Algorithms, JACM 1971. (This paper is free to down from ACM website)
Instead of prizes, it would be nice to have a prediction market on whether the problems will be solved by a certain date. This would work as a prize for the person who solves the problem, except it's more fair, in the sense that people who prove a big (but not final) step of the proof can also benefit from the prize money.
ReplyDeleteToo bad anti-gambling law don't allow something like this.
It's probably the same post as the previous reference, but there is a classical lower bound of Omega(n log n) for element distinctness in any comparison based algorithms. If the algorithm is not comparison based, there are various tricks one could make, from the counting/radix sort (if the numbers not to large) to all kind of other options that would actually sort the numbers, let alone find duplicates.
ReplyDeleteYears ago (my god - 94?) I coauthored a survey paper with Adleman on open problems in number theoretic complexity. Surprisingly little progress has been made on those...no doubt due to the fact that few people work in the subfield any more. One of the biggies - primes in P was solved.
ReplyDeleteIncidentally I have a bet with Ron Fagin on how P=NP will be resolved. I got 5 to 1 odds!
Ryan wrote:
ReplyDeleteor -- it's related to finding the best rate for parallel repetition of a simple family of 2P1R games
but what about foams, man? what's it got to do with the foams??? I just can't wait till CCC!
Wet foams vs dry foams. Surface tension keeps the surface area small.
ReplyDeleteI regularly post open problems on my blog. Here are two recent examples; the former has generated quite a bit of good discussion. Occasionally I give open problems as projects for my students...
ReplyDeleteThe 20th Century view is that a list of open problems provides a view of the underlying & fundamental unity of mathematics (in the tradition of David Hilbert).
ReplyDeleteA 21st Century view might be, that the list of fundamental mathematical theorems is exponentially long, and therefore, open problem lists are necessarily a very sparse sampling of a set possessing unbounded structural complexity.
Any such list is necessarily designed to meet human needs equally as much it is inspired by a search for eternal truth.
In other words, don't open problem lists (both past and present) reflect mathematical truth and human nature in roughly equal measure?
any bets on who will win the acm doctoral dissertation award this year?
ReplyDeleteor at least any takes on the strongest theory thesis eligible for the award?
Why not add the feature to complexity zoo itself? It would not be too much of a hassle, and it would be more appropriate.
ReplyDeleteWhy not add the feature to complexity zoo itself?
ReplyDeleteMy complexity zoology expert system, which is linked from complexity zoo, recognizes the difference between incomplete data (which is marked gray in the Javascript diagram) and open problems (which are marked green). Open cases may be the weakest side of the current dataset, and I would certainly welcome more feedback.
But there is a serious problem with the Complexity Zoo site and even more, Complexity Zoology. Namely, TCS has largely move beyond relations among complexity classes and onto other problems. Except for the quantum classes, both projects are largely a review of the 1960s through the 1990s. It is hard to get the attention of the experts today, although they still respect these old results.
As it happens, Robert Samal and myself (Matt DeVos) have just created a wiki for open problems. It is more or less in a beta form at the moment, but we think this is an idea whose time has come. We haven't settled on a name yet, but the url is as follows:
ReplyDeletehttp://dm.irmacs.sfu.ca
We are keen for contributions and suggestions.
Matt DeVos
Sorry for my sloppyness, here is the linkable url for our new page:
ReplyDeleteOpenmap
Matt DeVos