One of the things that regularly prompts me to refresh this stackexchange is the promise of interesting open problems (and not "wide" open problems like major complexity class separations or the complexity of factoring/matrix multiplication/etc).
Encoded in this are three qualities I am looking for. Each are mildly subjective but I hope the general idea is communicated:
- Open/important (to somebody).
- Natural/interesting.
- Not "wide" open. By "wide" I mean the problem is probably not solvable with current techniques.
There have been some seriously cool open problems posted. There is in fact even a tag 'open-problem' used to demarcate questions involving open problems. (The two "seriously cool" examples I linked to are both on this list.)
However, I am worried that the list of questions tagged with 'open-problem' is not complete. For example, here is a question that is open, not demarcated with the 'open-problem' tag but that meets the criteria I listed above. This seems to happen with regular frequency: a question is posted, it is resolved soon thereafter that the question has been open in the literature for some time, yet the question is not then given the 'open-problem' tag.
I was wondering if we could compile and keep updated (an ultimately subjective) list of open problems meeting the above criteria which are not given the 'open-problem' tag. A list like this is interesting to me, and I am sure will be interesting to other members. It will be easier to justify the site to newcomers and can help compile some of the most intriguing question for pursuits like the poster for STOC.