Open Problem Garden - forum topic - Comments

simple-to-state open problems (re: Give us your suggestions!)

Anonymous — Sat, 27 Oct 2012 06:14:24 +0200

why not take an open problem that is hard to explain and find an equivalent simple-to-state question so an amateur might find something about the problem?

thanks (re: Question about 'solving' something)

niekeaerts — Thu, 24 Nov 2011 17:57:30 +0100

Sorry. And thanks, I will follow this procedure next time!

Best, Nieke

Re: Is this garden still in use? (re: Question about 'solving' something)

Robert Samal — Thu, 24 Nov 2011 16:35:23 +0100

Sorry for slow response. The garden is definitely in use, only a bit slow moving right now. For that particular problem, read my comment there. As a general rule: we usually mark the problem as solved only after the paper about it goes through a peer-review process -- but definitely one should wait till somebody "in the know" verifies his proof or counterexample.

Best wishes, Robert

Is this garden still in use? (re: Question about 'solving' something)

niekeaerts — Thu, 24 Nov 2011 15:33:41 +0100

As nobody responded, I just changed the solved-identity. I guess, if this garden is still in use, now I'll get a response ;)

New Mexico Machinery (re: Topics: Theoretical Computer Science)

Anonymous — Wed, 20 Jul 2011 11:14:06 +0200

I believe I put forth more topics than are currently needed and therefore order them in decreasing important as categories. Note that, by arguing how important a field is as a topic, I am not arguing how important or large the field itself is. Thank you.

GreenTent Design (re: Topics: Theoretical Computer Science)

Anonymous — Thu, 24 Feb 2011 07:00:22 +0100

This is the proper name of the field. "Complexity Theory" could also be confused with a number of fields with similar names. Thank you.

My topology areas (re: Maintaining questions in a subject area)

porton — Sun, 05 Sep 2010 23:24:22 +0200

Hi moderators,

I have submitted several open problems which appeared in the course of my research.

Moderators moved all my problems into "Second tier problems" section. I believe moderators did it because my research is not yet published.

Robert, I hope that you will move them back to Topology section after I will publish the research where I define the problems. I hope not in vain, don't I? I hope to publish that article during a year.

Afterward we should have a special subsection of Topology (or may be better of Topology/General) for my problems. I suggest to name my section "Funcoids & Reloids" ("theory of funcoids and reloids" is an other name of "Algebraic General Topology", AGT for short).

--
Victor Porton - http://www.mathematics21.org

Re: Topology sub-areas (re: Maintaining questions in a subject area)

Robert Samal — Sun, 05 Sep 2010 23:01:17 +0200

Hi,

the project is certainly not dead, only other duties prevent the original contributors from submitting new problems these days ...

Anyways: let me know what subareas (and possibly subsubareas) would make sense for topology. This requires a moderator, but we will do it promptly.

Many thanks for your contributions!

Robert Samal

However these are your posts :-) (re: Maintaining questions in a subject area)

porton — Sat, 04 Sep 2010 23:59:29 +0200

"New problems appear regularly".

However I noted that many of these are posted by you, rybu :-)

Anyway Open Problem Garden is not dead.

What is the approximation of its grow time going to infinity? It is a fundamental mathematical question :-)

--
Victor Porton - http://www.mathematics21.org

It is not dead (re: Maintaining questions in a subject area)

porton — Sat, 04 Sep 2010 23:21:46 +0200

It is certainly not dead, new problems appear regularly. Just forum activity is low.

Regarding your question: Common users cannot create new (sub)areas, sadly.

--
Victor Porton - http://www.mathematics21.org

Proposed topics (cont 6) (re: Topics: Theoretical Computer Science)

cwenner — Sat, 04 Apr 2009 18:25:44 +0200

(continuation of prev post)

New subtopics:

\item(!) Complexity > Class Relations Large area and important as a category. Relations between complexity classes, a "pure complexity theory". Might need a better name. \item(!) Complexity > Randomness in TCS This is a vaguely defined but large area. Somewhat important as a category. The name possibly needs to be clarified so that algorithm construction questions goes under "Algorithms" rather than "Complexity". \item(!) Complexity > Circuit Complexity Large area. Important as a category. \item() Complexity > Descriptive Complexity Medium-small size and not very important as a category. Could also go under "Logic".

(the end)

(Parametrized algorithms would be better than Fixed-Parameter Tractability)

Proposed topics (cont 5) (re: Topics: Theoretical Computer Science)

cwenner — Sat, 04 Apr 2009 18:07:42 +0200

(continuation of prev post)

Subtopics of complexity: Current ones:

\item(?) Derandomization Somewhat small. I suggest introducing "Randomness in TCS" and removing this one. \item(?) Hardness amplification Small subtopic. I suggest removing. \item(!!) Hardness of approximation Large and important topic, keep. \item() Interactive proofs \item() PCP These two are essentially the same and almost solely used for "hardness of approximation". They are however large enough to justify a separate subtopic so I suggest merging these two into just "Proof systems". Questions about MA may very well go in here as well.

(see next post for cont)

Proposed topics (cont 4) (re: Topics: Theoretical Computer Science)

cwenner — Sat, 04 Apr 2009 18:07:10 +0200

(continuation of prev post)

Less important:

\item(??) Algorithms > Heuristics Large but not sure what mathematical questions there are. \item(?) Algorithms > Online algorithms and competitive analysis Medium-small size. Not very important as a category. Some overlap with data structures. \item() Algorithms > Fixed-Parameter Tractability Medium-small size. Modern topic. Not very important as a category. \item() Algorithms > Average-case and smoothed analysis Medium-small size. Traditional but not very active topic. Not very important as a category. \item(??) Algorithms > Algorithm Analysis / Algorithm Theory / Techniques I wish there were an active area like this.

(see next post for cont)

Proposed topics (cont 3) (re: Topics: Theoretical Computer Science)

cwenner — Sat, 04 Apr 2009 18:06:41 +0200

(continuation of prev post)

Possible future topics:

\item(??) Algorithms > Numerical Analysis. Medium size with respect to problems? I really don't know what mathematical problems there are here. Not sure if this should go under "Scientific Computation" until necessary to split. \item(!) Algorithms > Computational Geometry Medium size. Somewhat important as a category. I know that there are plenty of algorithm problems here. Some overlap with approximation and data structures. Not sure if this should go under "Scientific Computation" until necessary to split. \item() Algorithms > Computational Biology Medium size. Not very important as a category. I know that there are plenty of algorithm problems here. Some overlap with approximation. Not sure if this should go under "Scientific Computation" until necessary to split.

(see next post for cont)

Proposed topics (cont 2) (re: Topics: Theoretical Computer Science)

cwenner — Sat, 04 Apr 2009 18:06:01 +0200

(continuation of prev post)

Subtopics of algorithms:

\item(!?) Algorithms > Data Structures Large category with plenty of overlap. Whenever possible, a problem should go into a more specific category. \item(!) Algorithms > Approximation Algorithms Medium size. Somewhat important as a category. \item() Algorithms > Graph Algorithms I suggest moving/duplicating this subtopic from Graph Theory or else one may argue that there should be similar "Algorithms" subtopics in the other subjects. \item(?) Algorithms > Mathematical Programming Medium size. Important as a category. Some overlap with approximation and numerical analysis. \item(?) Algorithms > Quantum Computation Medium size. Hot topic. Somewhat important as a category. \item(??) Algorithms > Scientific Computation This is a broad area that might be split into their own subtopics or even its own topic if enough problems are posted.

(see next post for cont)