23
$\begingroup$

This is the official site FAQ for Theoretical Computer Science. This question will contain a list of questions, with each question linking to a single answer. If there is prior discussion on an answer, or you wish to discuss a particular answer, please create a separate meta question and link to it (so that this FAQ remains uncluttered).

The scope of this site:

How to use this site:

How to help the site:

This site is run by YOU, and your help is needed to maintain it as a valuable resource for the community. Here are some ways in which you can help (once you acquire enough reputation points):

Best practices:

Please use this thread if you have suggestions for improving this FAQ.

$\endgroup$

21 Answers 21

Reset to default
14
$\begingroup$

How do I write formulas?

This site uses MathJax. You can simply type (almost) any LaTeX equations between a pair of $-signs, and the system will display it properly typeset. This should work in questions, answers, and comments (with some exceptions).

Why don't I see any formulas? Why do I get a [Math Processing Error]?

Try this page first and see if MathJax works in your system at all. If the demo page works, but formulas on this site don't work, try to clear your browser's cache.

Related discussion: [1] [2] [3] [4]

$\endgroup$
1
  • 2
    $\begingroup$ I think MathJax behavior has changed. You no longer need the "double-backslash trick." For instance, $A = \{a,b,c\}$ works as $A = \{a,b,c\}$, which is perfect. $\endgroup$
    – Sadeq Dousti
    Commented Dec 15, 2010 at 13:43
13
$\begingroup$

What kind of questions are too basic?

Our aim is to ask and answer research-level questions in theoretical computer science. "Research-level" means, roughly, questions that might be discussed between two professors, or between graduate students working on Ph.D.'s, but not usually between a professor and the typical undergraduate student. It does not include questions at the level of difficulty of undergraduate homework. Here are some examples of questions that are off-topic because they are not research-level or because they are too easy:

  • Questions that can be easily answered by reading a Wikipedia article on the topic.
  • Questions that can be easily solved by Googling.
  • Questions that are solved by browsing one of these web sites.
  • Typical homework problems in textbooks.

If you do not think that your question is research-level but you cannot find an answer in above options, you may want to try https://math.stackexchange.com/.

Related discussion: [1] [2] [3]

$\endgroup$
1
9
$\begingroup$

When should I downvote/upvote?

First of all, try to vote often. You have a budget of 30 votes per day, and it is perfectly fine to use up your daily quota.

Here are some guidelines that you can use to decide whether you should upvote, downvote, or not vote at all:

  • Upvote only questions and answers you understand but do so whenever they are of high quality. To evaluate quality for a question think of whether it is interesting, whether it is at the appropriate level, whether it is well formulated. To evaluate quality for an answer think whether it addresses the question and whether you learned something from it. Above all, use your judgement.

  • Downvote a question only if it is clearly not at the appropriate level or it is clearly not well formulated. Downvote an answer only if it is technically wrong, or does not address the question, or is so badly formulated that it is impossible to understand. You should leave a comment explaining why you downvoted whenever you do so, unless that would duplicate an already existing comment.

  • You should ignore a question/answer's current score when you decide on your vote.

You can't upvote or downvote your own question/answer.

Related discussion: [1] [2] [3]

$\endgroup$
9
$\begingroup$

Do I need to use my real name?

You do not have to, but you are strongly encouraged to use your real name. We hope that this site will become a valuable resource for the research community, and that reputation earned here will translate into reputation outside as well. Using your real name will help make that connection.

We also hope that research discussions on this site will occasionally lead to actual citations in papers, or even new research ! From that perspective, using your real name will help immensely.

Related discussion: [1] [2]

$\endgroup$
7
$\begingroup$

Useful resources

Complexity classes:

  • Complexity Zoo. In questions that are related to complexity classes, it's a good idea to first check the Zoo and see if your question is already answered there – or if it's a well-known open problem. The Zoo also defines the standard naming convention for complexity classes on this site.

Hardness and approximability:

Problems related to graph families:

Related discussion: [1]

$\endgroup$
3
  • $\begingroup$ proposals: wikipedia.org scholar.google.com oeis.org $\endgroup$
    – Radu GRIGore
    Commented Sep 7, 2010 at 11:56
  • $\begingroup$ @Radu GRIGore: new suggestions are posted there, not here. $\endgroup$
    – Kaveh Mod
    Commented Aug 2, 2011 at 2:56
  • $\begingroup$ Zoo is a deadlink; see the archive. $\endgroup$
    – J_H
    Commented Feb 15, 2023 at 18:04
6
$\begingroup$

My (wonderful!) question was closed! What do I do now?

There are many reasons a particular question might be closed. Don't be discouraged if this happens to you!

Many such questions have a lot of merit but are closed for reasons that may not have occurred to you. You should consider re-asking your question after reading the comments others leave and adjusting your presentation.

If, after reading through the rest of this FAQ, you have additional concerns about how to effectively formulate your question, post a new question on meta.cstheory.stackexchange.com and link that question to the original source.

Related discussion: here

$\endgroup$
6
$\begingroup$

My answer turned out to be incorrect. What should I do?

There is no perfect rule telling you what to do in such cases. Here are some of the options:

  • Edit it to a correct answer. In this case, leaving a comment to the answer explaining the edit might be also a good idea.
  • Leave it as it is after adding a clear notice that it is incorrect and an explanation of why at the beginning of the answer.
  • Delete it.

The consensus seems to be that leaving only a comment about incorrectness is not sufficient because readers will not notice it until they read the comments.

An incorrect answer clearly marked as such is often informative because it shows an incorrect approach which other people may think is correct. Therefore, some people consider that we should not delete an answer just because it is incorrect.

Related discussions: [1] [2]

$\endgroup$
6
$\begingroup$

When to use "community wiki"?

The "community wiki" (CW) flag should be reserved for questions where either (i) you do not believe that there exists one (or even a few) good answers, and where any individual response contributes a small enough piece of the overall answer that no reputation increase is warranted, or (ii) you want to encourage other users to edit your answer or question, perhaps if you realise there are gaps in your answers that you would like other users to fill in.

CW is irreversible. When in doubt, do not mark a question CW – this can always be changed later. A crucial technical point: any answers made to a CW question will themselves be CW.

Often, a question that seems like it should be CW can be modified to be more direct and focused, thus avoiding the need for the tag. For example, the seemingly CW question "What are the key papers in topic X" can often be reworded as the more focused "What I should start reading when studying topic X". The latter has one or a few definite answers and need not be made CW.

If a question or answer is CW, there is something of an invitation to edit it: the reasons for editing are broader for CW posts than non-CW posts.

Related discussion: [1] [2]

When to mark an answer as "community wiki"?

Anyone can edit a CW (community wiki) answer and no one earns reputation for it.

One good use of the CW flag is to aggregate multiple answers into a single one with uniform formatting. Another possible use of the CW flag is to invite others to fill in an incomplete answer. (Perhaps you only have time to sketch the idea, or perhaps you do not know the complete answer but have a strong hunch that your idea points in the right direction.)

This answer is flagged CW for good reason: There's room for improvement.

$\endgroup$
2
  • 2
    $\begingroup$ A quick note: Part of this no longer applies because, as of today, the option to declare questions as community wiki became a privileged action which only moderators can use (meta.stackexchange.com/questions/67581/…). Answers can still be declared as community wiki as before. $\endgroup$
    – Tsuyoshi Ito
    Commented Oct 14, 2010 at 15:06
  • $\begingroup$ @Tsuyoshi, I edited taking into account your comment. Don't forget this is a CW answer too. :) $\endgroup$
    – Radu GRIGore
    Commented Feb 9, 2011 at 14:21
5
$\begingroup$

What is the policy on crossposting to/from MathOverflow or other StackExchange sites?

Crossposting from MathOverflow and other StackExchange sites is perfectly fine, as long as they aren't done in parallel. That is, if you post a question on one site, you should only post to the other site after you have not received a satisfactory answer for some time, and you should provide a link in each post (or in the comments on it) to the other one. As a courtesy, if you post your question here after trying MathOverflow or another StackExchange site, please try to integrate in your question the answers you received on MathOverflow/the other site (even if they did not answer everything).

Related discussion: [1] [2] [3]

$\endgroup$
0
4
$\begingroup$

Questions about Theorem X in paper Y?

It is perfectly fine to ask very specific questions like this:

How does one reach eq 3.14 from eq 3.13 in paper X, page Y? I tried the following ... but it didn't work.

However, if you suspect that there is a mistake in a paper, it might be polite to first contact the authors by email before posting a question here.

Related discussion: [1] [2]

$\endgroup$
4
$\begingroup$

Why can't I comment on my own question?

Ideally, you should always be able to comment on your own question.

If you cannot find a link labeled “add comment” below your own question, you may be using a different account from the one you used to post the question. Note that using the same user name and the same icon does not mean that you are using the same account.

If this happens, ask the moderators to merge the two accounts by flagging the question and state the situation briefly in the flagging comment. Alternatively, you can open a thread on meta to explain the situation.

To prevent this from happening in the future, we strongly encourage you to register your account.

Related discussion: [1]

$\endgroup$
2
  • 2
    $\begingroup$ I realized that a user needs 15 rep points to flag a post and 5 rep points to post on meta. This means that a new user (including a user who lost a browser cookie for his/her own unregistered account) cannot use either of the suggestions in this answer. We need a better way to handle this. $\endgroup$
    – Tsuyoshi Ito
    Commented Jun 12, 2012 at 2:46
  • $\begingroup$ I remember a discussion about using answers for commenting when a user doesn't have enough reputation. $\endgroup$
    – Kaveh Mod
    Commented Jun 12, 2012 at 4:16
3
$\begingroup$

How do I delete my own question/answer?

The conditions to delete a post is explained in detail on meta.stackoverflow.com. If you can delete your post, there is a link labeled “delete” below your post (on the same line as “link” and “flag.”)

If you have not registered, you cannot delete a post. To delete your post in this case, register first and then try to delete it. If you still cannot, you may have an unregistered account which is not merged to your registered account. In this case, ask moderators to merge your unregistered accounts into the registered one.

$\endgroup$
3
$\begingroup$

How do I copy-and-paste a formula?

Right-click on it, and select "Show Source". You can try it here: $\sum_x 2f(v_x)^2$. Note that the MathJax menu (which contains the item “Show Source”) may be behind the context menu of your browser.

Related discussion: [1]

$\endgroup$
3
$\begingroup$

There are too many questions on boring topic X that I don't care about. What should I do?

Tagging provides a mechanism to filter out topics that you aren't interested in, and retain topics that you are. On the right of the front page you will see two lists: interesting tags and ignored tags. If you enter tags relating to subjects you care about (and the system will auto-suggest based on what you type), then questions tagged with those tags will be highlighted in the main list.

Conversely, if you add tags for topics you don't care about, any question containing those tags will be hidden from view. If a question contains both interesting and ignored tags, it will be displayed with a faded color.

It's easy to delete tags from either list just by clicking on the little cross.

$\endgroup$
3
$\begingroup$

What kinds of tags should I use?

Each question should have at least one "ArXiv tag", and any number of additional tags (there is a limitation of at most 5 tags per question and at most 24 characters per tag). Try to re-use existing tags whenever possible, but you are also welcome to propose new tags. See this page for our current list of tag synonyms.

ArXiv tags

[FIXME: add answer]

Related discussion:

  1. arXiv tags vs not?
  2. Proposal: Remove discipline prefix from the Arxiv-style tags

[soft-question]

A soft-question is subjective and argumentative without a precise answer and can be a question about theoretical computer science rather than being a question in it.

Examples:

  • How would you teach X to undergrads?
  • Why computer scientists do X when Y happens?
  • Is theoretical computer science part of pure math?
  • How long will it take to settle P vs NP in your opinion?

More discussion.

[big-picture]

A big-picture question is higher-level question, and although it can be subjective and argumentative it does not need to be, and is a question in theoretical computer science.

Examples:

  • What is the main idea behind Razborov-Rudich natural proofs?
  • What are the obstacles to prove a super-polynomial lower-bound for SAT?
  • Where did the idea of Domain theory came from?
  • What are the main objects and constructions used in crypto?
  • Is there a program to settle Unique Games Conjecture?
  • Is polynomial time Turing computable the right definition for feasible computation?
  • What evidence do we have for Church-Turing thesis?

More discussion.

$\endgroup$
2
$\begingroup$

What if I see a question that I think is inappropriate/off topic/offensive ?

(this may need to be factored into multiple answers)

One of the most important ways in which you can help this site flourish is by making sure that the questions listed on it reflect the true interests of the community. A general procedure to follow if you have issues with a question is:

  1. If it's a matter of scope, check this FAQ entry.
  2. If the question is incoherent or unclear, suggest in comments ways in which the original poster (OP) might fix it.
  3. If there's a disagreement, initiate a discussion on meta. Cross link the meta discussion and the original post.
  4. If you have enough reputation, you may choose to vote to close the question. In that case, please post your reason as a comment and link to a meta discussion thread.
  5. If the question is offensive, or spam, you can flag it and a moderator will deal with it.
  6. If you wish to bring this question to moderator attention for any other reason, flag it.
$\endgroup$
2
$\begingroup$

What is meta ? Why do people keep telling me to go there ? I just want my question answered !!

CSTheory is a Q&A site, so it's geared towards asking and answering questions, rather than general discussions. Often, a discussion breaks out regarding the merits of a question or its suitability on the site. Also, you might have a general question about using the site that isn't covered in this FAQ. For this purpose, there's a "meta" site where you can post such questions.

As a general rule, if you have any questions/discussions about a particular question or set of questions, post a new question on meta.cstheory.stackexchange.com and link that question to the original source.

$\endgroup$
2
$\begingroup$

Are questions about [this area of computer science] on-topic here?

As our FAQ explains, we interpret "Theoretical Computer Science" broadly. Roughly speaking, the subareas of computer science that put emphasis on mathematical technique and rigor are on-topic.

Here are some further clarifications regarding possible borderline cases:

  • Pure math: if the problem has some applications in theoretical computer science, it is welcome here – more discussion.
  • Artificial intelligence: theoretical aspects of artificial intelligence are on-topic; philosophical questions are probably off-topic – more discussion.

Further discussion: [1] [2]

$\endgroup$
1
$\begingroup$

I did a search for a tag, and a mislabelled question came up. what do I do ?

If you have enough reputation points, you can retag mislabelled questions. This is important to make sure tags reflect the true content of the question, which makes searching and filtering easier. Please use the tagging guide to decide what the right tags should be.

$\endgroup$
1
$\begingroup$

Can I discuss questions and answers on the site?

In addition to questions and answers, cstheory.sx supports, like other Stack Exchange sites, comments on questions and answers. This supports discussions, and is important to improving posts, challenging possible mistakes, and bringing attention to relevant resources.

Of course, discussions only work if the participants know of the comments. Besides comments appearing after the question or answer they comment on, the author of the question or answer will see that you have commented, as will anyone who you have notified by @name, where the site tries to figure out who @name might be by looking at the user names of other users who have participated in the thread. You need at least the first three characters of the user name for the site to figure out that the @nam might be about them. For more details on comment replies, see “How do comment replies work?” on meta.stackoverflow.com.

$\endgroup$
0
$\begingroup$

My question is not a research-level question in TCS, where can I ask it?

For questions other than research-level questions in TCS, you may want to consider the following places to ask:

$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .