login/create account
Topics: Theoretical Computer Science
What topics and subtopics should there be under the subject "Theoretical Computer Science"? Just more specific than the "Give us your suggestions" thread.
GreenTent Design
On February 24th, 2011 Anonymous says:
This is the proper name of the field. "Complexity Theory" could also be confused with a number of fields with similar names. Thank you.
Proposed topics
On April 4th, 2009 cwenner says:
I propose a number of additional topics below. 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. In particular, I am trying to assess how many open problems may be expected to fall under these categories and how important it is that these problems do not fall under other subtopics. Obviously, my estimates are based on my own naive perception and I'm not an expert. I have therefore, additionally, added a number of exclamation marks (!) to indicate how important I believe a suggestions is and a number of question marks (?) to indicate my uncertainty.
(See next post for continuation)
Proposed topics (cont 1)
On April 4th, 2009 cwenner says:
(continuation of previous post)
I suggest changing the topic "Complexity" to "Computational Complexity Theory" as this is the proper name of the field. "Complexity Theory" could also be confused with a number of fields with similar names.
I suggest changing the topic "Coding Theory" to "Information Theory" as it is a broader topic and "Coding Theory" can be introduced as a subtopic if necessary. We have to accept a good deal of overlap for problem garden to work.
Additional topics of Theoretical Computer Science:
- \item(!?) Automata, Languages, and Computability. These (sub)topics may instead go under "Complexity" or "Logic", or a combination thereof. Topics: **! Automata and formal Languages; **? Recursion Theory \item(??) Artificial Intelligence Topic: **! Machine Learning (this area has good mathematical problems)
(see next post for cont)
Proposed topics (cont 2)
On April 4th, 2009 cwenner says:
(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)
Proposed topics (cont 3)
On April 4th, 2009 cwenner says:
(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 4)
On April 4th, 2009 cwenner says:
(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 5)
On April 4th, 2009 cwenner says:
(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 6)
On April 4th, 2009 cwenner says:
(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)
Drupal
CSI of Charles University
New Mexico Machinery
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.