652

Next: About this document ...

WEBPAGE FOR CMSC 652

Fall 2007

Syllabus: syll.ps,syll.pdf

hw must be handed in typed- LaTeX is recommended. Here is a guide to math in latex: math.ps,math.pdf

If you want to download the latex code which produced math.ps and math.pdf its here: math.tex

HANDOUTS

Computability Theory: comp.ps,comp.pdf
Known Theorems: known.ps,known.pdf
P, NP, and PH. np.ps,np.pdf
Randomization rand.ps,rand.pdf
Jon Katz's lecture on lower bounds on 1-tape Turing Machines, katz.ps,katz.pdf
Parity-SAT notes (Number of Satisfying Assignments) number.ps,number.pdf
Sparse Sets Notes- I (only used the stuff about -reductions. sparse.ps, sparse.pdf
Sparse Sets Notes- II - the Mod stuff sparseMOD.ps, sparseMOD.pdf
Sparse Sets Notes- III - Turing Reductions sparseT.ps, sparseT.pdf
Sparse Sets Notes- IV - SAT in coNP with SPARSE oracle sparseY.ps, sparseY.pdf
SAMPLE MIDTERM midsam.ps, midsam.pdf
Regular Expressions with Squaring (Needed for Oral HW 8). regexp.pdf
Graph Isom notes giam.ps, giam.pdf
Promise Problem Example for AM ampromise.ps, ampromise.pdf
The slides for Tom's talk on parallelism. parallel.ps
More on AM moream.ps, moream.pdf
Trading Group Theory for Randomness trading-group-theory.pdf
PCP writeup (by someone else). pcp-writeup.ps pcp-writeup.pdf
Amy's proof of that thing about Graph Isom that I couldn't quite get right. (NOTE- not to worry, won't be on final.) amy.ps amy.pdf
Complexity Theory Drinking Game. drinkinggame.ps drinkinggame.pdf
Sample Problems. finalsam.ps finalsam.pdf
Study Guide. study.ps study.pdf