This is an open thread for any topic not covered in other posts. Please feel free to discuss whatever you wish here (but keep it polite, constructive, and at least tangentially connected to the polymath enterprise.)
24 Comments »
RSS feed for comments on this post. TrackBack URI
I am not sure exactly where to post suggestions for polymath projects that one is not willing to run (I don’t have the time or energy to maintain one myself), but I thought I would toss out a problem in computational complexity that has always bugged me. It is a problem that is easy to state, probably will succumb to elementary methods, and probably could be solved if enough people contributed ideas. Here goes: consider the usual subset sum (or is it knapsack?) problem where you are given a list of positive integers N_1, …, N_k, and a target number T, and you must decide whether there is some subset of N_1, …, N_k that sums to T. The problem is to beat the “trivial algorithm”, which I shall describe presently.
The first thing to realize is that there is a subset sum equal to T iff there is one equal to S-T, where S=N_1 + … + N_k. Furthermore, subsets of size t summing to T correspond uniquely to subsets of size k-t summing to S-T. In this way, you only need to consider subsets of size at most k/2 (and check whether they sum of T or S-T) to solve the problem. But now you can use the usual “collision technique” to reduce the problem to subsets of size at most k/4, by forming a table of all subsets of at most this size, along with their sum of elements, until you find a disjoint pair of subsets that sums to either T or S-T. The running time of this procedure should be comparable to (k choose k/4) = c^(k+o(k)), for a certain constant c that is easy to work out. This is what I mean by the “trivial algorithm”. Now, the problem is find an algorithm — any at all — that runs in time at most d^k, where d < c. To my knowledge no such algorithm is know to exist!
Comment by Ernie Croot — July 29, 2009 @ 5:14 pm |
Thanks for the problem! We are planning to organise another polymath project beyond the primes one (which already has a strong computational complexity component to it), and this may well be a candidate if we can find people to run it (one lesson we’ve learned so far is that engaged leadership is quite important to make these things run smoothly). I do know that there is some interest in the CS community in running these things, so this may well be a good candidate.
Edit: I’ve set up a wiki page at http://michaelnielsen.org/polymath1/index.php?title=Other_proposed_projects to collect projects of this nature.
Comment by Terence Tao — August 3, 2009 @ 2:20 pm |
I have developed an algorithm for this problem as well as a target range. In essence it is based on determining the largest number that can be selected without exceeding the target by the size of the smallest number selected. This technique manages to provide an efficient way of selecting subsets such that if any one of the selected numbers is deselected the result will be less than the target, (for a single target). It also is easily adapted to determining multiple subset totals from a single set. This was inspired from problems in oil delivery delivery logistics, and how to fill vehicles. As to it’s worst case performance I’m not sure how to go about determining this.
Comment by John Bufton — September 13, 2009 @ 8:15 pm |
Wordpress seems to be marking some of my posts in the research thread as spam (or holding them for moderation, at minimum?) — understandable, perhaps, given a high posting rate, wordiness, and a tendency to link externally, but annoying. I suppose it’s possible that I’m the only one being affected, but it seems unlikely. Is there any way to loosen the restrictions to minimize the number of legitimate comments that aren’t immediately posted?
Comment by Harrison — August 9, 2009 @ 8:13 pm |
Unfortunately there doesn’t seem to be an option to reduce the stringency of the spam filter (other than to raise the threshold of external links, which I’ve upped to five), but I will try to check it daily.
Comment by Terence Tao — August 9, 2009 @ 8:53 pm |
I have been contacted by someone about possibly writing an article about polymath. I have some questions about how to handle this. For instance they mentioned us possibly having a spokesman and it is not clear that we have that. We might want to consider having some sort of organizational structure to deal with the media. For one thing there are a lot of potential readers for something like this and that could result in more people entering future polymath’s. Another issue that comes to mind is that they wanted to see something about people talking about their experiences with polymath and we have several threads already dealing with that but I don’t think there is one central hub for referring to all of these.
Comment by Kristal Cantwell — August 12, 2009 @ 6:49 pm |
Hmm, I’m actually a bit surprised that we have media attention at all… but if there are inquiries then certainly we could discuss them on this blog (John Baez recently did something similar when he was solicited by the Notices of the AMS to talk about blogging). Tim is probably the most obvious person to contact, being the one who originated the whole polymath idea and being involved in all of the polymath projects to date.
Comment by Terence Tao — August 12, 2009 @ 9:57 pm |
I gave Tim’s name to them. It is the Notices, I think they want to do a feature article on blogging as well as polymath in addtion to what John Baez is writing.
Comment by Kristal Cantwell — August 13, 2009 @ 1:57 am |
Let me make a comment about the checks and X’s: Some kind of “Are you sure you want to Check (or X) that comment?” query needs to be added to the wordpress page. Just today I was trying to look up a last minute comment to include in my NSF grant proposal, and the mouse point moved over someones comment, and I accidentally clicked the check. I thought that if I then clicked the X, it would erase what I had done, but instead it added another X, and kept the check (or maybe there wasn’t really a check added in the first place — it seemed like there was, though).
Comment by Ernie Croot — October 1, 2009 @ 8:16 pm |
Yes, this is a problem – there should be a mechanism to “uncheck” a comment back to the neutral mode. My plan at this point is to collect a list of grievances so that when the time comes to move to a better platform, we will know what features to implement. (#1 on the list is the ability to preview and edit comments.)
Comment by Terence Tao — October 1, 2009 @ 11:27 pm |
I have suggested 3 problems to be solved collaboratively:
http://portonmath.wordpress.com/2009/08/30/proposal-conjecture-complementive-filters/
http://portonmath.wordpress.com/2009/10/17/proposal-partitioning/
http://portonmath.wordpress.com/2009/10/20/complete-lattice-generated-by-a-partitioning-of-a-lattice-element/
(note that the last two seem being closely related) and also I suggested a bigger “research writing” project:
http://portonmath.wordpress.com/2009/08/29/polymath-filters-on-posets/
I have the hope that at least one of my projects will be selected by the Admins.
However you may follow the above URLs which contain pingbacks to other my blog posts, and note that I wrote it a little messy (because of automatically generated pingback comments instead of hand-crafted comments). Is that OK?
I have the incentive and time to host and moderate the research thread and the discussion thread, but I’m unsure whether I started correctly. Please reply me with an explanation on how I may re-organize my blog posts. Maybe I should (when one of my projects will be officially selected) post two new blog posts to start the research thread and the discussion thread?
Or maybe, somebody other would host the discussion on the blogs? I feel not very important whether it will be done by myself or somebody other, but I feel I need to ask for a little guidance. Well, I feel indeed that I am able to be a good moderator for these my own projects.
Comment by porton — October 25, 2009 @ 7:20 pm |
Thanks for the contributions! Currently we are not planning any new projects on this blog in the near future, but this may change if one of the proposals picks up momentum of its own accord (this happened with the finding primes project).
The key seems to be to find a project which would already attract a significant number of interested (and capable) volunteers, but it’s not always easy to predict in advance what projects people find both (a) interesting, and (b) able to contribute to…
Comment by Terence Tao — October 27, 2009 @ 10:30 pm |
You’ve said: “The key seems to be to find a project which would already attract a significant number of interested (and capable) volunteers, but it’s not always easy to predict in advance what projects people find both (a) interesting, and (b) able to contribute to…”
My problems (see above) has the advantage that they (AFAIK) do not require any special knowledge. Every mathematician knows lattice theory. Not every mathematician knows number theory and computational complexity theory, which seem main competitors for my tasks.
Comment by porton — October 28, 2009 @ 6:09 pm |
I suspect it’s the “(a) interesting” part that an expository book on lattices will have trouble with…
Comment by Scott Morrison — October 29, 2009 @ 3:14 am |
I never suggested to write an expository book on lattices.
Among my suggestions there are a half expository half research book on filters on posets and generalizations thereof:
http://portonmath.wordpress.com/2009/08/29/polymath-filters-on-posets/
(Certainly it is related with lattices but isn’t an “expository book on lattices”.)
I’m not sure whether my theory of filters in interesting for general mathematical audience. (The theory of filters is mainly a technical not beautiful theory, however there I introduce some concepts which count to be beautiful, e.g. my theory of filtrators and related “core parts” and “dual core parts” is a beautiful part of the theory.) However the theory of filters is important for my further research “Algebraic General Topology”:
http://www.mathematics21.org/algebraic-general-topology.html
“Algebraic General Topology” is certainly a beautiful and interesting theory and I even hope to receive Abel Prize for that:
http://www.mathematics21.org/abel-prize.html
Comment by porton — October 29, 2009 @ 12:26 pm |
Hehe… from http://math.ucr.edu/home/baez/crackpot.html:
21. 20 points for suggesting that you deserve a Nobel prize.
I suppose the Abel prize will do, too.
Comment by Scott Morrison — October 29, 2009 @ 11:37 pm |
I might add that it’s not really up to Terry and me to select a project. If you want to start a project then you can. As the other replies above make clear, the main necessary condition for it to be successful is that you should attract the interest of other mathematicians. I think the best way of doing that is to give a more detailed post in which you say exactly what the project would be and what you don’t know how to do at the moment. If you have thought hard about the problems already, then you should be able to write an account that takes the reader to the point where you don’t know how to continue. Often a precisely posed problem that “ought to be doable” is exactly the hook that is needed for another mathematician to be interested. Have you got some of those?
If you do produce a detailed post, I will be happy to publicize it on my blog, and also on this blog.
Comment by gowers — October 29, 2009 @ 2:21 pm |
Dear Gowers, I’m now busy. (I work as a programmer.) When I will have free time I will write a longer explanation about “complementive filters are a complete lattice” problem
http://portonmath.wordpress.com/2009/08/30/proposal-conjecture-complementive-filters/
I’ve chosen it from the three problems because:
1) I feel it more important than two other problems, and there are other important problems to prove which it may be used (if true).
2) I can think more about possible ways to attack this problem than the two other.
Comment by porton — October 29, 2009 @ 7:37 pm |
Trying to write an exposition on the “complementive filters are a complete lattice” problem, I was going to write a proof of its certain special case. Trying to write this I noticed that I stumble over an open problem even in this special seemingly simple case.
This is the problem over which I stumbled:
http://portonmath.wordpress.com/2009/10/31/are-principal-filters-the-center-of-the-lattice-of-filters/
So I will attempt to settle this littler problem before going to the exposition of the original problem:
http://portonmath.wordpress.com/2009/08/30/proposal-conjecture-complementive-filters/
If the little problem over which I stumbled appears to be difficult also, I may offer it for a separate polymath project.
Comment by porton — October 31, 2009 @ 4:44 pm |
Oh, well. I already solved this “little problem”. Sorry for my comment in haste that it was unsolved.
The solution:
http://portonmath.wordpress.com/2009/10/31/principal-filters-are-center-solved/
To write a longer explanation of the “complementive filters are a complete lattice” conjecture remains my priority:
http://portonmath.wordpress.com/2009/08/30/proposal-conjecture-complementive-filters/
Comment by porton — October 31, 2009 @ 7:50 pm |
Dear Gowers,
I wrote a longer exposition about “complementive filters are a complete lattice” problem:
http://portonmath.wordpress.com/2009/11/02/exposition-complementive-filters/
I’m not sure whether it is in the state ready to be publicized. You may read it in order to test whether this my writing is understandable.
Also it contains a very short reference to the problem about coinciding quasidifference and second quasidifference. Should I write a longer explanation about that problem to attract more people? Or it is OK to just mention this problem because it is not the problem we are solving now?
Please say how well I wrote this and publicize if it is OK.
Comment by porton — November 1, 2009 @ 10:45 pm |
Dear Gowers,
I updated http://portonmath.wordpress.com/2009/11/02/exposition-complementive-filters/
adding there two new formulas as conjectures in the “Intersection with a set” subsection.
It is all I know about the “complementive filters are complete lattice” conjecture. I think this may be a starting point for other mathematicians who may be interested (personally I deem this an interesting problem).
I think that is does not extensively tells about “coinciding quasidifference and second quasidifference” is not a big defect, as it is an other problem and it may be not discussed here. Wiki reference where they may look for greater details on the full current state of that problem is available in this my exposition.
I ask you to publicize this my conjecture to be known for wider cycles of mathematicians. My blog visits are pretty low but this conjecture deserves wider attention.
Comment by porton — November 7, 2009 @ 9:17 pm |
I solved a problem which earlier proposed for one of polymath projects.
The problem was at
http://portonmath.wordpress.com/2009/11/29/co-separability/
See also this comment.
http://portonmath.wordpress.com/2009/11/29/co-separability/#comment-37
How to exclude the problem from the list of polymath proposals?
Comment by porton — January 18, 2010 @ 11:09 pm |
I’m interested in the platform for polymath. Clearly wordpress + wiki is not the desired model.
Are there any discussions of list of features one want from the platform?
Is it also possible to get financial support from any institution to develop such platform?
Comment by Mgccl — August 3, 2010 @ 4:11 pm |