User:Tcshasaposse/stylemanual: Manual of style

This page contains guidelines and recommendations for the style to be used in the TCS Wiki Project.

Objectives

The purpose of the TCS Wiki project is to improve coverage of theoretical computer science on Wikipedia. When writing articles, it is useful to keep in mind the following objectives:

• Provide an encyclopedic style reference for researchers and students from TCS and related disciplines. This audience is familiar with the basic ideas of TCS, but may lack knowledge in your area of expertise. To serve them, your article should aim to provide crisp and accurate but not overly technical information.

• Communicate the basic ideas and highlights of TCS to a general audience. This kind of audience will probably be unfamiliar with many of the basic concepts and will not be able to follow the "technical" parts of the article. There should be enough for them to get at least oriented. For them it should help have numerous links to other wikipedia articles.

• Attract curious young minds to TCS. Computer science is a fascinating topic for many high school and beginning university students from around the world. The TCS project can be used to pique their interest in the subject. To keep their attention it helps to put in some good stories and a bit of a personal touch: links to biographies of famous TCS people, historical remarks, popular science articles on the internet, and so on.

Structure of article

To achieve these somewhat conflicting objectives, you may find it helpful to structure the article in the following way. While these guidelines are not strict, please try to follow them so that all articles from the project meet a certain standard.

Do not write articles that are too long; consider splitting them into several sub-articles instead. If it takes too much scrolling, chances are people won't read it.

Preamble

The article should start with a sentence or two that situates your topic within the general context of theoretical computer science. For example, the article on probabilistically checkable proofs begins with

In computational complexity theory, a probabilistically checkable proof (in short PCP) is a type of proof that can be checked by a randomized verification algorithm with bounded query complexity.

The complexity class PCP is the class of decision problems that have probabilistically checkable proofs with completeness 1, soundness α < 1, randomness complexity O(logn) and query complexity O(1).

The PCP theorem states that PCP = NP.

The first sentence should begin by specifying the general area of your article (i.e. in theoretical computer science, in the theory of error-correcting codes) and proceed by giving an informal definition of the concept. The definition does not have to be too accurate; it is more important to provide links to other notions here.

The introductory section should not be more than 2-3 sentences long, and having only one sentence is okay. You may include short remarks about closely associated topics (e.g. the PCP theorem is closely associated to probabilistically checkable proofs), but resist the temptation of giving detailed explanations.

Definition

The definition should be technically accurate, but not overly detailed. Unlike the preamble, where links to other articles are a plus, the definition should be as self-contained as possible. For example, it is preferable to say

A pseudorandom generator is a function G such that the disttibution G(X) is not distinguishable from uniform by a so-and-so adversary

than

A pseudorandom generator is a function G such that the disttibution G(X) is pseudorandom.

Sometimes there are several possible definitions for a single notion, varying in degrees of generality or in more subtle ways. For example, should one require that a pseudorandom generator be efficiently computable? Should the class of adversaries be polynomials, circuits, or a general family of functions?

I don't think there is a single way to make these choices, but resist the temptation to do everything at once. One way is to give a specialized definition first, discuss its consequences, and then write a section on alternative definitions. Another way is to start with a general definitions and discuss various specializations of interest below.

Use the definition to introduce related notions and parameters. For example, the definition of probabilistically checkable proof can introduce the concepts of completeness, soundness, non-adaptivity, and so on. However, avoid confusing mathematical notation. For instance, instead of

A (S, ε)-pseudorandom generator is ...

consider saying

A pseudorandom generator of bias ε against adversaries of size S is ...

Other sections

While it is hard to come up with a single format of what should follow the definition, this could include some examples, highlights, and historical notes.

These parts of the article should be written in a way so that at least they make some sense to the non-expert. Stick to a high-level view but be accurate in your description. In particular, avoid as much non-standard notation as possible. For example,

X is a random variable sampled from the uniform distribution

is more desirable than

$X\sim {\mathcal {U}}$

This is not the place to prove your theorems! You can provide a few sentences of intuition about significant technical results related to the topic, but this is not the place to go into a lengthy discussion.

Historical references are highly desirable as they are likely to capture the imagination of the reader. For example, in the discussion on pseudorandom generators you could write:

Cryptographic pseudorandom generators were intruduced by Manuel Blum, Silvio Micali, and Andrew Yao in 1982.

Do not forget to include links to celebrities from our community.

References

It is hard to give a complete list of references, so use your best judgement. References to original work are not all that useful. Instead is better to put in a textbook that might be more accessible to non-experts. Online materials (e.g. the Arora-Barak complexity book) are great.

It is better if references are reviewed and more permanent. Avoid linking to blog entries. Links to lecture notes are okay but keep in mind that they are moved or deleted from time to time, and some of them are fairly technical.

Typography

When typesetting mathematical text, do not make excessive use of the math environment, especially inline. Text typeset in math mode often looks oversized and ugly. Think twice before using it: Sometimes you can say the same thing in words and avoid introducing unnecessary notation.

While mathematical notation is imperfect in html mode, it is often visually better. Make sure you italicize variables properly, e.g. f(x). Use boldface for operators and complexity classes, e.g. E[f(x)], NP. Avoid overusing superscripts and subscripts.

Things to avoid

See the article on pseudorandom generator theorem. This material can be found in much better form in many textbooks and lecture notes. It is as useless for the expert as it is for the curious bystander. Articles like this can cause more harm than good.

Do not try to do too much at once. It may be better to start at the bottom and work our way up to the top. Some articles (e.g. computational complexity) leave much to be desired but should be much easier to handle once the proper infrastrucure is set up (definitions of basic complexity classes, subareas of research, etc.)