62:
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
160:
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
394:
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.
381:
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.
53:
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
288:
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,
72:
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.
169:
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
385:
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.
45:
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.
338:
157:) 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.
438:) 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.)
222:
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
76:
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.
346:
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.
84:
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
428:. 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.
244:
can introduce the concepts of completeness, soundness, non-adaptivity, and so on. However, avoid confusing mathematical notation. For instance, instead of
285:
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.
349:
Historical references are highly desirable as they are likely to capture the imagination of the reader. For example, in the discussion on
398:
While mathematical notation is imperfect in html mode, it is often visually better. Make sure you italicize variables properly, e.g.
85:
241:
434:
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.
93:
425:
154:
226:
be efficiently computable? Should the class of adversaries be polynomials, circuits, or a general family of functions?
150:
35:
124:
that have probabilistically checkable proofs with completeness 1, soundness α < 1, randomness complexity O(log
435:
237:. Another way is to start with a general definitions and discuss various specializations of interest below.
350:
233:. One way is to give a specialized definition first, discuss its consequences, and then write a section on
313:
223:
121:
43:
Provide an encyclopedic style reference for researchers and students from TCS and related disciplines.
301:
105:
26:
This page contains guidelines and recommendations for the style to be used in the TCS Wiki
Project.
240:
Use the definition to introduce related notions and parameters. For example, the definition of
63:
of famous TCS people, historical remarks, popular science articles on the internet, and so on.
17:
114:
38:
on
Knowledge. When writing articles, it is useful to keep in mind the following objectives:
411:
297:
149:
The first sentence should begin by specifying the general area of your article (i.e. in
362:
215:
358:
134:
366:
51:
Communicate the basic ideas and highlights of TCS to a general audience.
373:
Do not forget to include links to celebrities from our community.
229:
I don't think there is a single way to make these choices, but
190:) is not distinguishable from uniform by a so-and-so adversary
34:
The purpose of the TCS Wiki project is to improve coverage of
406:). Use boldface for operators and complexity classes, e.g.
325:
357:
Cryptographic pseudorandom generators were intruduced by
316:
332:
430:Articles like this can cause more harm than good.
416:. Avoid overusing superscripts and subscripts.
231:resist the temptation to do everything at once
104:) is a type of proof that can be checked by a
344:This is not the place to prove your theorems!
8:
324:
323:
315:
7:
333:{\displaystyle X\sim {\mathcal {U}}}
60:Attract curious young minds to TCS.
86:probabilistically checkable proofs
24:
242:probabilistically checkable proof
106:randomized verification algorithm
98:probabilistically checkable proof
94:computational complexity theory
426:pseudorandom generator theorem
272:ε against adversaries of size
108:with bounded query complexity.
1:
151:theoretical computer science
128:) and query complexity O(1).
36:theoretical computer science
206:such that the disttibution
182:such that the disttibution
452:
436:computational complexity
351:pseudorandom generators
307:is more desirable than
235:alternative definitions
334:
266:pseudorandom generator
254:pseudorandom generator
224:pseudorandom generator
200:pseudorandom generator
176:pseudorandom generator
155:error-correcting codes
335:
314:
302:uniform distribution
68:Structure of article
424:See the article on
153:, in the theory of
330:
353:you could write:
300:sampled from the
122:decision problems
18:User:Tcshasaposse
443:
339:
337:
336:
331:
329:
328:
260:consider saying
120:is the class of
115:complexity class
451:
450:
446:
445:
444:
442:
441:
440:
422:
420:Things to avoid
392:
379:
312:
311:
298:random variable
283:
167:
82:
70:
32:
22:
21:
20:
12:
11:
5:
449:
447:
421:
418:
391:
388:
378:
375:
371:
370:
341:
340:
327:
322:
319:
305:
304:
282:
281:Other sections
279:
278:
277:
258:
257:
220:
219:
202:is a function
192:
191:
178:is a function
166:
163:
161:explanations.
147:
146:
130:
129:
110:
109:
81:
78:
69:
66:
65:
64:
56:
55:
47:
46:
31:
28:
23:
15:
14:
13:
10:
9:
6:
4:
3:
2:
448:
439:
437:
432:
431:
427:
419:
417:
415:
414:
409:
405:
401:
396:
389:
387:
383:
376:
374:
368:
364:
363:Silvio Micali
360:
356:
355:
354:
352:
347:
345:
320:
317:
310:
309:
308:
303:
299:
295:
292:
291:
290:
286:
280:
275:
271:
267:
263:
262:
261:
255:
251:
247:
246:
245:
243:
238:
236:
232:
227:
225:
217:
213:
209:
205:
201:
197:
196:
195:
189:
185:
181:
177:
173:
172:
171:
164:
162:
158:
156:
152:
144:
140:
136:
132:
131:
127:
123:
119:
116:
112:
111:
107:
103:
99:
95:
91:
90:
89:
87:
79:
77:
74:
67:
61:
58:
57:
52:
49:
48:
44:
41:
40:
39:
37:
29:
27:
19:
433:
429:
423:
412:
407:
403:
399:
397:
393:
384:
380:
372:
348:
343:
342:
306:
293:
287:
284:
273:
269:
265:
259:
253:
249:
239:
234:
230:
228:
221:
216:pseudorandom
211:
207:
203:
199:
193:
187:
183:
179:
175:
168:
159:
148:
142:
138:
137:states that
125:
117:
101:
97:
88:begins with
83:
75:
71:
59:
50:
42:
33:
25:
359:Manuel Blum
135:PCP theorem
390:Typography
377:References
367:Andrew Yao
165:Definition
100:(in short
30:Objectives
321:∼
54:articles.
369:in 1982.
80:Preamble
365:, and
276:is ...
256:is ...
296:is a
252:, ε)-
214:) is
194:than
16:<
270:bias
133:The
113:The
96:, a
268:of
248:A (
139:PCP
118:PCP
102:PCP
92:In
413:NP
410:,
361:,
264:A
198:A
174:A
143:NP
141:=
408:E
404:x
402:(
400:f
326:U
318:X
294:X
274:S
250:S
218:.
212:X
210:(
208:G
204:G
188:X
186:(
184:G
180:G
145:.
126:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.