How to Present a Paper in Theoretical Computer Science: A

How to Present a Paper in Theoretical Computer Science:

A Speaker’s Guide for Students

∗

Ian Parberry

†

Department of Computer Sciences

University of North Texas

There are many points in your career at which you will be called upon to present a paper in

Theoretical Computer Science, perhaps a paper written by somebody else in a graduate seminar,

or your own research at a conference, departmental colloquium, or job interview. This skill is

particularly important if you intend to pursue a career in academia. While research excellence is

the main criterion for success as a theoretical computer scientist, your career will be assisted if you

gain a reputation as a competent speaker. A competent speaker will more likely be invited to give

colloquia at leading universities and invited talks at important conferences than a mediocre one,

provided their research is of similar quality. The expected quality of the presentation can be the

deciding factor in the selection or rejection of a controversial conference paper in cases where there

is no clear consensus from the program committee.

The author does not claim to be an expert in oral presentation, but has attended enough bad

talks to be able to draw up a few rules of thumb. This note is written primarily for students

in Theoretical Computer Science, but most of it is relevant to other sub-disciplines of Computer

Science, and some to any scientiﬁc discipline. Diﬀerent styles of presentation work for diﬀerent

people. These guidelines are intended to assist you in developing a workable style of your own.

The remainder of this note is divided into four sections. The ﬁrst, “What to Say and How to Say

It”, concentrates on choosing and organizing the material to be presented. The second, “Getting

Through to the Audience”, focusses on presentation. The third, “Visual and Aural Aids”, discusses

the proper use of overhead projector transparencies and the microphone. The fourth, “Question

Time”, is devoted to the period after the talk during which the audience asks questions of the

speaker. An earlier version of this note has appeared in [2, 3].

1 What to Say and How to Say It

The selection of material to include in a talk, and how it is arranged and presented is crucial to

success.

Communicate the Key Ideas

Most new results are obtained by using a few key ideas or tricks, plus the application of standard

tools and techniques. Make sure that your talk emphasizes the key ideas and skips over what is

standard, obvious, or merely complicated.

∗

 Ian Parberry, 2000.

†

Author’s mailing address: Department of Computer Sciences, University of North Texas, P.O. Box 311366,

Denton, TX 76203–1366, U.S.A. Electronic mail should be directed to [email protected].

Don’t get Bogged Down in Details

This rule cannot be over-emphasized. Many speakers launch right into the technical details from

the start, confusing and alienating most, if not all of the audience. Remember that you will have

been thinking deeply about the material for months or even years, whereas most of the audience

will either hear about the subject matter for the ﬁrst time during your talk, or at best will be very

rusty. Things that you take for granted will have to be explained carefully.

Details are out of place in an oral presentation. After all, anybody with modest technical skills

can ﬁll in the details by studying the paper at leisure, and anybody lacking technical skills will

want to hear about the details even less. The audience would appreciate an overview of the paper

so that they can determine whether the paper is worth reading. A good talk motivates the listener

into reading the paper and makes the task of reading it easier.

Structure Your Talk

Your presentation should be broken into several distinct parts, each with its own objectives and

style. Each part should be clearly delineated. The audience should be steered gently from one part

to the next. A well-structured talk is easier to understand than a rambling, unstructured one, and

it also makes more eﬃcient use of time.

Use a Top-down Approach

The following is a template for producing a talk. It consists of four parts; the Introduction, the

Body, Technicalities and the Conclusion. The Introduction is a general, informal description of the

paper. The Body gives a more formal, but abstract description, and the Technicalities section takes

a detailed look at a critical part of the paper. The audience is thus introduced to the material in

a top-down fashion. The Conclusion concisely summarizes the key results, and wraps up the talk.

Naturally, very few talks will ﬁt this template exactly, since the structure of a talk varies greatly

with subject matter, length of presentation, author, presenter, and audience. The Introduction and

the Conclusion are fairly standard, but there is ample room for customization in the other two parts.

For example, some complicated subjects may need several passes, each of successively greater detail,

instead of the two-pass body-technicalities scheme described below. You should use this template

as a starting point only. Don’t be afraid to be innovative.

The Introduction

This is possibly the most important part of your presentation. It sets the tone for the entire talk.

It determines whether the audience will prick up their ears, or remain slumped in their chairs.

A lot of snap decisions about your competency are made before the Introduction is over. First

impressions are very important.

• Deﬁne the Problem

An amazing number of speakers forget this simple point. No matter how diﬃcult and technical

the problem, it can usually be described succinctly and accurately in under ﬁve minutes. This

time is well invested. If the audience doesn’t understand the problem being attacked, then

they won’t understand the rest of your talk.

• Motivate the Audience

Explain why the problem is so important. Throw in a little philosophy if necessary. How does

the problem ﬁt into the larger picture? If it involves a model of a real-world phenomenon, then

how good is the model? What are its applications? What makes the problem nontrivial? You

can return to these issues in the Conclusion, when you can re-address them with the beneﬁt

of hindsight.

• Introduce Terminology

The use of terminology and jargon should be kept to a minimum, but is impossible to avoid

entirely. All terms must be introduced early. It is also useful to remind the audience of the

deﬁnitions at critical points later in the talk.

• Discuss Earlier Work

Research is not usually carried out in a vacuum. There will almost always be other relevant

or related work, which you should describe. Present an orderly synopsis of these previously-

obtained results. A table is often used for this purpose. Be sure to mention the author of

each paper and its date of publication. Compare and contrast them with each other and with

your paper.

• Emphasize the Contributions of your Paper

Make sure that you explicitly and succinctly state the contributions made by your paper.

The audience wants to know this. Often it is the only thing that they carry away from the

talk. Don’t make the audience search for the information in a morass of details — they may

get it wrong.

• Provide a Road-map

Give the audience a brief guide to the rest of the talk, along the lines of the last paragraph of

the introduction to this note. But don’t make it a dry litany of dull generalizations (“ﬁrst I

will present the introduction, then summarize earlier work, then present the main body, and

end with the conclusion”). Instead, give a short preview of what will be in each section. This

part of the talk can be eliminated for very short conference presentations.

The Body

This contains the meat of your presentation, and is the point at which the attention of the audience

will start to waver if you messed up your Introduction.

• Abstract the Major Results

Describe the key results of the paper. You may present the statements of the major theorems,

but not their proofs. You will probably have to get a little technical here, but do so gradually

and carefully.

• Explain the Signiﬁcance of the Results

Pause, and explain the relationships between the formal theorems that you have just presented

and the informal description that you gave in the Introduction. Make it clear to the audience

that the results do live up to the advance publicity. If the statements of the theorems are

very technical then this may take some time. It is time well-spent.

• Sketch a Proof of the Crucial Results

The emphasis is on the word “sketch”. Give a very high-level description of the proofs,

emphasizing the proof structure and the proof techniques used. If the proofs have no structure

(in which case it may be assumed that you are not the author of the paper), then you must

impose one on them. Gloss over the technical details. It is a good idea to point them out but

not to explore them.

Technicalities

If you are doing well, then most of the audience will have followed you up to this point. However,

the experts may be in danger of getting bored. The more cantankerous among them may not

believe your results, since you have presented them only in high-level terms. Now you can give

some technical details. This will also help the non-expert to see what is really going on behind the

scenes, lest he or she is lulled by your polished style into thinking that it is all too easy.

• Present a Key Lemma

Choose just one key result. It should be important, non-trivial, should give the ﬂavour of the

rest of the technical details and should be presentable in a relatively short period of time.

• Present it Carefully

You may descend into messy technical details, but try to be as succinct and clear as possible.

You might want to ﬁll in one of the gaps that may appear in the paper, to give the audience

something that they could not get by staying home and reading the paper. (Almost all

technical papers contain small gaps. Lack of space usually prevents proofs from appearing in

all their gory detail.)

The Conclusion

Your aim here is to round oﬀ the talk neatly. You should discuss the results brieﬂy in retrospect

placing emphasis where it is needed.

• Hindsight is Clearer than Foresight

You can now make observations that would have been confusing if they were introduced

earlier. Use this opportunity to refer to statements that you have made in the previous three

sections and weave them into a coherent synopsis. You will regain the attention of the non-

experts, who probably didn’t follow all of the Technicalities section. Leave them feeling that

they have learned something nonetheless.

• Give Open Problems

It is traditional to end with a list of open problems that arise from your paper. Mention

weaknesses of your paper, possible generalizations, and indications of whether they will be

fruitful or not. This way you may defuse antagonistic questions during question time (see

Section 4).

• Indicate that your Talk is Over

An acceptable way to do this is to say “Thank-you. Are there any questions?”.

Know Your Audience

Make sure that your talk is prepared at the right level. There are four types of audience that you

will most likely meet.

1. Scientists

Most of the audience won’t even know what Computer Science is. Emphasize the Introduction

and the Body. Omit the Technicalities section. Remember that you will have to deﬁne many

terms that you have taken for granted for years. Provide more philosophical background.

Ordinarily you will not meet this kind of audience until later in your career.

2. Computer Scientists

Most of the audience will not know what Theoretical Computer Science is. You can introduce

a small Technicalities section, but keep it brief. Be careful with your deﬁnitions. The emphasis

should remain on the Introduction and the Body. This type of audience will be typically

encountered during job interviews and departmental colloquia.

3. Theoretical Computer Scientists

You will no longer need to be quite so careful with deﬁnitions, but it is politic to provide

reminders for the rusty, the young and the less mentally agile in the group. The emphasis

should be on the Body of the talk, but the Technicalities section need no longer be muted.

This type of audience will typically be encountered during departmental colloquia and major

theory conferences.

4. Experts

If you address experts in your ﬁeld, then you can get right down to the core of the matter.

The emphasis should be on the Body and the Technicalities. Keep in mind that the more

experts there are in the audience, the more argumentative they are likely to be. This type of

audience will be typically encountered during small, specialized conferences and workshops.

2 Getting Through to the Audience

Once you have selected and organized your material, the next major hurdle is when you ﬁnd yourself

actually standing in front of the audience. Faulty delivery can ruin even a well-prepared talk.

Use Repetition

Oral presentations may be summed up as follows: “Tell them what you’re going to tell them. Tell

them. Then tell them what you told them”. In the Introduction you tell them what you are going

to tell them. In the Body and Technicalities you tell them. In the Conclusion you tell them what

you told them. Don’t be scared of this repetition. Sometimes repetition is the only way to clarify

misconceptions. Naturally, this means that you should repeat things in diﬀerent ways, and not

quote yourself verbatim. If you have studied Coding Theory, then you will know the importance of

redundancy when communicating over a noisy channel. The channel between ears and intellect is

extremely noisy.

Remind, don’t Assume

If your paper assumes a “standard” result in your ﬁeld (for example, the Church-Turing Thesis,

Cook’s Theorem, etc.), it is worthwhile to provide your audience with a brief reminder of exactly

what the result is. Phrasing it as a reminder avoids antagonizing those who for various reasons are

not familiar with it (for example, those who work in a diﬀerent ﬁeld, the absent-minded, or students)

by allowing them the opportunity to learn while hiding their ignorance, and avoids antagonizing

those who are familiar with it by allowing them to “tune out”.

Don’t Over-run

There is very little that is more exasperating than listening to a talk that drags interminably past

its scheduled ﬁnishing time. The author has observed that the quality of a talk is almost always

inversely proportional to the time that it over-runs. Unless it is explicitly stated otherwise, when

you are told that the talk is to last for x minutes, plan to talk for at most x − 5 minutes, and

leave 5 minutes for question-time. If in doubt about the proportions, then enquire. Departmental

colloquia generally last for ﬁfty minutes, and conference presentations from ﬁfteen to thirty minutes,

including question-time. Don’t try to cover too much material. As you gain more experience you

will learn how much you can cover in any given period. Until then, you will have to rehearse your

talk until it is the correct length. A forty-ﬁve minute departmental colloquium must naturally diﬀer

greatly in composition from a ﬁfteen minute conference presentation. If you are short of time, the

ﬁrst thing to cut is the Technicalities section.

Maintain Eye Contact

Maintain eye contact with your audience. Spread your attention throughout the audience instead

of concentrating on any one person or group (even if they are the only ones who matter). A good

strategy for beginners is to choose a few people at random in diﬀerent places in the audience, and

look at them successively. If presenting at a conference, be sure to glance periodically at the session

chair, who will signal you when you are running out of time.

Control Your Voice

Speak clearly and with suﬃcient volume. Don’t speak in a monotone. Avoid information-free

utterances (“Um, ah, er”, etc.) Avoid fashionable turns of phrase. Avoid hype.

Control Your Motion

Project energy and vitality without appearing hyperactive. Use natural gestures. Try not to remain

rooted in one spot, but avoid excessive roaming. Don’t get between the projector and the screen.

Try not to fall oﬀ the dais, if there is one (speakers with true sang froid will continue to talk without

interruption after they have fallen from the dais, even if they are momentarily invisible).

Take Care with Your Appearance

Good grooming and dress helps, but avoid appearing overly ostentatious. A jacket and tie for men

and professional attire for women is important at a talk given as part of a job interview, but casual

dress is de rigeur for colloquia and conference presentations.

Minimize Language Diﬃculties

English appears to be the common language for theoretical computer scientists of all nations. If

you are called upon to deliver a talk in a language in which you are not completely ﬂuent (be it

English or otherwise), the eﬀect of your deﬁciencies in language will be minimized if you pay careful

attention to all of the other aspects of your talk described in this note. It is a good idea to get

a native speaker to look over your transparencies before you deliver the talk. At all costs, try to

avoid speaking from a prepared text. In general, theoretical computer scientists are accustomed

to, and tolerant of foreign accents and modes of speech.

Try Not to Get Anxious

It is easy to become anxious and nervous during a talk, and forget all of the advice in this note. The

best antidote for this is experience. Anxiety can be reduced by making sure you prepare adequately

beforehand, and practice the talk in front of fellow students or your faculty adviser. It is a good

idea to spend 10–15 minutes alone before the talk calmly looking over your slides and organizing

your thoughts. One sure way to increase anxiety is to pay undue attention to the reaction of the

most important person in the audience. The pained expression on his or her face may be the result

of last night’s pizza, not your presentation. If you ﬁnd yourself panicking during a talk, it is best

to pause, close your eyes, take a few deep breaths, calm yourself, and then continue. If you botch a

few talks, it will not be the end of your career. What will be remembered about you is the quality

of your research, not the quality of your ﬁrst few talks.

3 Visual and Aural Aids

Now that you have a well-prepared talk and can deliver it with style, there is the next stumbling

block: the overhead projector and the microphone.

Use Overhead Projector Transparencies

The accepted method of presentation diﬀers from one academic community to another. In the

Liberal Arts, a speaker generally reads dispassionately from a prepared text with or without the

assistance of 35mm slides that contain only pictures and diagrams. In Mathematics, a speaker

generally speaks oﬀ-the-cuﬀ with the aid of a blackboard or whiteboard. In the Sciences, a speaker

generally uses 35mm slides or overhead projector transparencies as an adjunct to their talk. The

standard in Theoretical Computer Science is to use overhead projector transparencies.

A talk appears more polished when you prepare overhead projector transparencies in advance.

When speaking away from home, always make sure in advance that an overhead projector is avail-

able. Your hosts will be able to provide one under most circumstances. You may prepare your

transparencies by hand if necessary, but if you will be travelling and giving the talk many times,

the transparencies will survive longer if you produce them mechanically. It is often a matter of

machismo for young theoreticians to prepare their transparencies by hand at 2 a.m. the night

before a FOCS or STOC conference presentation. However, very few of these people consistently

give above average presentations, and you are ill-advised to emulate them at least until you are

more experienced.

Make Legible Transparencies

If your normal writing is a chicken-scrawl, then you probably should use a computer to prepare your

transparencies. If this is impossible, you must take great pains to ensure that your writing is legible.

Make sure that the text is large enough to be read from a distance. Normal-sized handwriting and

12-point type are unacceptable, but 18-point type is generally considered adequate.

Use standard document preparation software to produce large-type copy; the author uses SliT

(see Lamport [1, Appendix A]), which automatically produces text in a large, easy-to-read font.

This can be printed directly onto transparencies using a laser-printer, or the hardcopy can be

photocopied onto the transparencies. Make sure in both instances that you are using transparencies

that are made for photocopying, otherwise the high temperatures inside the machine will bake the

transparency onto the drum, which will make you highly unpopular with everybody except the

repair person. The preparation of slides by computer has an added bonus: you can use spelling

checkers to discover many obvious errors.

Don’t Overload Transparencies

Don’t put too much on each transparency. Try not to write full sentences. Write down deﬁnitions,

important points, key-words and phrases. The transparency is an adjunct to your talk; it should

be used for emphasis, to resolve ambiguity, for precision and for the retention of information over

a short period of time. It does not contain a transcription of your talk. A good transparency

underlines the key points for the audience and simultaneously acts as a prompter or cue-card for

the speaker.

Don’t Use Too Many Transparencies

A common mistake is to prepare too many transparencies. This indicates that your talk contains

too much material. If you change transparencies too often, then the audience will not have time

to digest each one properly. There should be enough time to read each transparency several times

while the speaker is talking. The number of transparencies per talk will vary from person to

person, and will depend upon the type of material being presented, and the amount of text on each

transparency. Allow an average of 1.5 to 2 minutes for each transparency. Very short conference

presentations are an exception to this rule, in which case one minute per transparency can be

managed with eﬀort and practice.

Avoid Slide Covering

Avoid situations where you want to show only part of a transparency. Make two transparencies

instead. Many people object to “slide covering”, the act of covering part of the transparency with

an opaque object such as a sheet of paper to prevent the audience from seeing it. It is hard to do

gracefully. The cover sheet will invariably slide oﬀ, and you will lose valuable time and savoir faire

in retrieving it. The use of overlays is equally frowned upon when used for this purpose.

Use Overlays Properly

Overlays are acceptable when you need to make small and incremental changes to a complex

transparency. They can be used to great eﬀect in the right circumstances. Overlays come in

two forms. In the ﬁrst form, two or more transparencies are successively placed on top of each

other as the talk progresses. This is to be avoided since transparencies are typically hard to align

in the ﬁrst place, and are easily dislodged. In the second form, the overlays are fragments of a

transparency that are taped to the outer edges of the main transparency, folded back at the start of

the presentation, and ﬂopped over onto the transparency at the appropriate moments. This is far

preferable to the ﬁrst form, but you should avoid constructing transparencies that have so many

overlays that they resemble a hedgehog. Do not tape the overlays to the center of the transparency.

Adhesive tape is not as transparent as it seems, and will usually show up as a ragged shadow on

the screen.

It is wise to avoid the over-use of overlays, particularly with portable overhead projectors. In

the latter the light source is above the transparency and hence must pass through the transparency

twice, compared to once for the traditional projector with the light source below the transparency.

Transparencies may look transparent, but they are actually slightly opaque: a stack of as few as six

of these on a traditional projector, or three overlays on a portable projector, may appear almost

completely opaque under some lighting conditions.

Use Colour Eﬀectively

The use of colour can enhance a presentation, particularly when used in moderation in the ﬁgures

and diagrams. The colour of the text can be changed periodically, but it is most eﬀective when there

is a clear motivation (a simple example may be to put the statements of theorems in a diﬀerent

colour from the rest of the text). At all costs avoid the temptation to produce a rainbow of text.

Some colours are more visible than others. Yellow is almost always invisible.

Use Pictures and Tables

Remember the old cliche “A picture is worth a thousand words”. However, be sure to explain the

signiﬁcance of your diagrams and tables. There is nothing more mystifying than a sequence of

esoteric, unlabelled, unexplained pictures. “Our results look like this” is not suﬃcient explanation.

In this context, the cliche should be modiﬁed to “A picture plus a hundred words is worth a

thousand words”.

Beware of the Microphone

You will probably need to use a microphone during a conference presentation. The session chair

should assist you to attach it to your clothing. It typically consists of a small box which goes into

a pocket, and a very small microphone on a clip which should be attached to your clothing as close

to your face as possible (preferably on the collar or the upper part of the tie, if you are wearing

one). The microphone is attached to the box with a short wire, and the box is attached to the

ampliﬁer by a long wire.

Instead of a clip, the microphone may have a loop of string that goes around your neck. If it

is long enough, pass it over your head. If not, it should detach from one side of the microphone so

you can pass it around your neck. It is usually hard to detach and reattach, particularly when it is

out of sight under your chin and you are nervously facing several hundred people for the ﬁrst time.

If you are clumsy in attaching the microphone, or unlucky enough to drop it, there will be a loud

unpleasant scraping or impact noise heard over the speaker. To avoid this, there is often a small

switch on the box which deactivates the microphone during the attachment. Use this switch, but

don’t forget to reactivate it.

The microphone will be dislodged by brushing against it while gesturing, knocking the box out

of your pocket, snagging the short wire, or stepping on or getting tangled in the long wire. This will

of course result in a loud noise and a loss of time and concentration while replacing the microphone.

If you roam while you speak, be aware of the microphone and its wires.

4 Question Time

As we have already seen, it is customary to end a presentation with a short period for questions.

You can expect to receive three types of question. The ﬁrst is the genuine request for knowledge,

which should cause you no diﬃculties if you are adequately prepared. The second is the selﬁsh

question, in which the questioner merely wishes to draw attention to him or herself and elicit

wonder at his or her ability to devise such an incisive and cogent question. It is politic to take a

few seconds to compose an erudite reply that directly or indirectly compliments the questioner.

The third and most important category is the malicious question, in which the questioner

attempts to expose the speaker as a charlatan and a dissembler. This may come from one of two

possible motives. Unfortunately, there are many insecure people in our community who constantly

seek to build up their reputation by tearing other people down. Alternatively, particularly if you

are interviewing for a job, the question may be intended to see how you react to criticism under

pressure. Either way, expect to have your ego bruised occasionally. Equally under attack will

be your selection of problem (“boring, irrelevant, contrived”), your proofs (“harder than necessary,

well-known, a minor twist to an old technique”), and your references (“I published/read/discovered

something more interesting/general/diﬃcult a few years ago”). The best defense against this type

of question is to be prepared, be polite, and avoid getting involved in a lengthy exchange. It

is sometimes advisable to short-circuit such questions by oﬀering to take them oﬀ-line, since a

one-on-one discussion is likely to be less acrimonious than a public one.

Do not be afraid to answer “I don’t know” to some questions. Don’t, however, confuse “I don’t

know” with “it is not known”. Only say the latter when you are sure that the question is open. If

you have to say “I don’t know”, say it with assurance rather than meekness, and don’t be afraid

to approach your questioner after the talk — you might learn something.

5 Acknowledgements

The author would like to thank Virginia Holt for her comments on several drafts of this manuscript,

and a number of colleagues and students, including Don Coppersmith, Paul Howard, Pierre Les-

canne, Thomas Schwentick, and Kim Yates, for their useful suggestions.

References

[1] L. Lamport. L

X: A Document Preparation System. Addison-Wesley, 1986.

[2] I. Parberry. How to present a paper in theoretical computer science: A speaker’s guide for

students. SIGACT News, 19(2):42–47, 1988.

[3] I. Parberry. How to present a paper in theoretical computer science: A speaker’s guide for

students. Bulletin of the EATCS, (37):344–349, 1989.