Georgia Tech F’04

CS 8002 : PCPs and Hardness of Approximation

Lecture 0: Manual for Scribes

Lecturer: Subhash Khot Scribe:x

You will need to use the latex document processing system. This document is not a latex manual, but it does show you some basic tricks. Several good latex references exist on the web, and your grad colleagues should have books on latex. (My favorite is the Latex Companion.)

A file called template.tex already exists in this directory that wil take care of formatting. A file called macros.tex contains shorthands for math commands as well as for frequently used formatting tricks. Send me email if you have latex questions.

We are using the amsmath package for typesetting, which does a few things differently from standard latex.

Some tricks and tips appear below. Look in the source file howto.tex to understand how to do these tricks.

1 General Formatting Tips

1. Theorems, lemmas, corollaries, proofs, definitions, examples, exercises, remarks, etc. are typeset inside special environments. (The environment names are Thm, Lem, Cor, proof, Def, Exa, Ex, Rem respectively.) Here is how you write a theorem.

Theorem 1

If E denote energy, m denotes mass, and c denotes the speed of light, then

E = mc^{2}  (1)

2. File macros.tex also contains macros to typeset the following (not an exhaustive list): set notation (e.g. {1, 2, 3, 4}), cardinality of a set (e.g. |{1, 2, 3}|), Real and natural numbers (R, N respectively), probabilities (e.g. Pr[coin comes up head] = 1/2), Var[X] = E[X^{2}] − E[X]^{2}). If you want to add a new macro to macros.tex, please send me email. Do not edit macros.tex; I want all students to use the same version.

3. There are macros for writing pseudocode. Look in the source file to see how to generate the following piece of pseudocode.

input: G = (V, E), s, t output: yes if it discovers that t is reachable from s, and no otherwise

guess the distance k between s and t p := s for i := 1 to k do Figure 1: The bigger S′ is, the more likely h(S′) will hit a given point in {0, 1}^{m}.

non-deterministically pick a neighbor q of p p := q

if p = t then accept else reject

4. You can include figures by using the ffigure command. You first create a figure using xfig (on Unix) or Adobe Illustrator, save it as a postscript file (the subscript should be .eps) in the same directory as the latex files. Lets say this figure is 12sets.eps. Look in the source file to see how we can include this file and generate Figure 1.

If you get any error messages while including figures, check that the .eps file begins with %! and if not, edit out the first line or two of junk.

You will probably get better results if you draw the figures (in xfig or another program) in landscape orientation. Make it fill the entire page, since you can resize it when using the ffigure command.

2 General Math Formatting Tips

1. Use align to typeset a series of contiguous equations such as those occuring in a long derivation. (Do not use the old eqnarray command; it uses nonstandard typographical conventions.) In the source file you will see that an & tells the program which symbol to align on.

E = mc^{2}  (2)
E + H + G = t  (3)

Use the equation command for single equations.

E = mc^{2}  (4)

To mix text into math formulae, use the text command.

E = mc^{2}  (Einstein)  (5)

While presenting a sequence of calculations (using the align command) we sometimes need to say something briefly in the middle, say to explain a step. We can do this with the intertext command.

A + B + C + D + E = R + S  (6)

intertext: which can be upperbounded using the inductive hypothesis by

≤ Q + N  (7)

2. If no alignment is needed, we use gather to make the group of equations look neat.

a + b = b + a  (8)
(a + b) · (a − b) = a^{2} − b^{2}  (9)

3. There is also alignat for align type structures side by side.

L_{1} = R_{1}  L_{2} = R_{2}  (10)
L_{3} = R_{3}  L_{4} = R_{4}  (11)

4. Equations that do not fit into a line are typeset using the split environment, which allows alignment between lines using & as usual.

\begin{aligned}(a + b)^{3} − (c + d)^{3} − (a + d)^{3} & = a^{3} + b^{3} + 3ab(a + b) + c^{3} + d^{3} + 3cd(c + d) \\ & − (a^{3} + d^{3} + 3ad(a + d)) \end{aligned} (12)

5. To refer later to an equation, you need to label it with a label command. The command notag will make the equation unnumbered. The command tag will replace the equation number with some other designated symbol.

x^{2} − y^{2} = (x − y) · (x + y)  (13)
x^{3} − y^{3} = (x − y)(x^{2} + xy + y^{2}).  (∗)

Using (13) and (∗) we obtain

a + b = d  (14)

Now we give an unnumbered equation; note that the numbering resumes below

d + e = f

6. You can typeset equations involving “case” situations with the cases environment.

δ_{i,j} = \begin{cases}1 & if i = j \\ −1 & if i < j \\ 0 & otherwise \end{cases}  (15)

7. The matrix environment produces matrices. Below, we show the matrices produced

using matrix, pmatrix, bmatrix, vmatrix, Vmatrix respectively.

\begin{matrix}a & b \\ c & d \end{matrix} (\begin{matrix}a & b \\ c & d \end{matrix}) [\begin{matrix}a & b \\ c & d \end{matrix}] |\begin{matrix}a & b \\ c & d \end{matrix}| ∥\begin{matrix}a & b \\ c & d \end{matrix}∥

This environment can handle matrices with up to 10 columns. To produce a matrix like ( \begin{matrix}a & b \\ c & d \end{matrix} ) inside a text paragraph, use the smallmatrix environment and enclose with the appropriate parentheses. Try not to do this in the last line of the paragraph since that looks untidy, as here ( \begin{matrix}a & b \\ c & d \end{matrix} ).

8. To use bold-faced letters inside math equations, use mathbf command. To get bold numbers, greek symbols etc., use the boldsymbol command.

A_{∞} = α + d  (16)

9. Function and operator symbols (in addition to standard ones like sin, cos, log) can be defined using the operatorname command.

10. Typeset modular arithmetic using the pmod command.

x ≡ y + z (mod n).  (17)

11. You may be familiar with the frac command in latex. In practice one needs to distinguish typographically between fractions inside paragraph (such as \frac{x+y}{z^{2}+5}) and ones that occur in displayed equations, such as

\frac{x + y}{z^{2} + 5} = 8  (18)

The former use the tfrac command and the latter the dfrac command. One can also specify the parentheses around displayed fractions with fracp and fracb commands. The advantage of these is that the size of the parentheses will change automatically with the size of the display; compare (\frac{x+y}{z^{2}+5})with

(\frac{(\frac{x}{u}) + y}{z^{2} + 5}) = 5 = [\frac{x/u + y}{z^{2} + 5}]

12. Random examples of how to format some math expressions: \binom{n}{k}, exp(−x^{2}), x∧y ∨¬z, f : N → R.

3 Note on labels

IMPORTANT: When labelling equations, theorems, figures etc., use a prefix that includes the lecture number. For example lec5:eqn10 or lec5:fig6. Similarly, call your figures something like lec5fig1.eps instead of just fig1.eps. This will prevent naming conflicts when I try to latex the lecture notes all together.