What this Page is About
This is a page of links
to about six hundred transparencies
covering the seven of the nine chapters of the book
The Complexity
Theory Companion (Hemaspaandra and Ogihara, Springer-Verlag,
hardcover edition 2002; softcover edition 2010). For other information on this book,
see
the web
home page of The Complexity
Theory Companion.
Disclaimers of Various Sorts
These transparency sets are not
authored by either of the authors of the Complexity Theory
Companion (and we also do not maintain or correct them---they
are a free but take-it-as-it-is resource). Rather,
this transparencies in general are sets made, as a project, by various
groups of (typically very bright)
students who
took a course based on the book (and to whom we are deeply
indebted, for making this web page possible). The first transparency of the
set will announce the names of the authors of the transparency set.
Of course, as is typical, if you use these transparencies
sets for your own
courses, please do make sure to
credit the authors of the transparencies, via leaving their names on their
transparencies.
These transparencies in a few cases use nasty fonts or obscure 3rd party
software (e.g., powerpoint but with texpoint equations). So, if the
transparencies look crazy to you (most typically, the equations), that is
probably the reason. By the way, in Word/Powerpoint, such errors
happen flat-out silently. Sigh. And even a few of the pdf exports
here have this problem, due to problems the students had exporting in
tricky cases. But in most cases, even if you have problems with
using the Word/Powerpoint source, the .pdf or .ps versions should be
nicely printable to use as transparency masters.
Each transparency set presents just those aspects of its respective
chapter that the students decided to focus on, and so may not cover
every result or even every section.
If you are the author of one of these transparencies sets and
don't think it is properly here, let us know and we'll take yours
immediately down.
Transparency Sets For Seven of the Nine Body
Chapters of The Complexity Theory
Companion (note: Please see the first page of
each slide set for the names of
the authors of that slide set)
- Transparency sets for Chapter
1, The Self-Reducibility Technique.
- A set of 88 transparencies (written in 2015):
This set is
here as pdf.
Note: This transparency set diverges from the book in that it
does not present the left set technique, but rather uses
Mahaney's original "pseudocensus" proof of Mahaney's Theorem.
The left set technique is covered separately
in the 38-transparency set listed further down this page.
- A set of 109 transparencies (written in 2007):
This set is
here as pdf.
Note: Like the just-previous set, this transparency set diverges
from the book in that it does not present the left set technique, but
rather uses Mahaney's original "pseudocensus" proof of Mahaney's
Theorem.
- A set of 67 transparencies (written in 2006):
This set is
here as pdf.
Note: Like the just-previous set, this transparency set diverges
from the book in that it does not present the left set technique, but
rather uses Mahaney's original "pseudocensus" proof of Mahaney's
Theorem.
- A set of 35 transparencies (written in 2004):
As
a pdf export
and as
Word source (well, mostly source... about 1/3 of the transparencies
actually are based on
powerpoint source that in that .doc Word file is just inserted
as an image).
Warning: The Word source assumes that you have the
"Euclid" font set
installed on your machine... if not,
you'll silently get the wrong stuff showing when you view the Word
document.
Note: This transparency set diverges from the book in that it
does not present the left set technique, but rather uses
Mahaney's original "pseudocensus" proof of Mahaney's Theorem.
The left set technique is covered separately
in the 38-transparency set listed next.
- A set of 38 transparencies (written in 2001):
This transparency set's first part (14 transparencies) is
here as powerpoint
and its second part (the remaining 24 transparencies) is
here as powerpoint.
Note: This set focuses
completely on the left set technique, but does not cover the other
aspects of Chapter 1.
- Transparency sets for Chapter
2, The One-Way Function Technique.
- An set of 106 transparencies (written in 2015):
As
powerpoint source and as a
pdf export.
- An set of 49 transparencies (written in 2006):
As
postscript.
Note: This set for me views ok under gv (unix) and GSview (pc),
but not under ghostview (unix).
- A set of 102 or 103 (the pdf and the powerpoint differ by
one slide due probably to handling of overlays) transparencies (written in 2004):
As
a pdf export
and as
powerpoint source.
(Warning: The powerpoint was done using texpoint, so if you
don't have that, the powerpoint may be partially garbled.)
- An set of 25 transparencies (written in 2000):
As
a postscript export
and as
powerpoint source.
Note: The 102-side set above covers the chapter very carefully,
and completely,
and even covers the difficult part on associative one-way functions.
In contrast,
this 25-transparency set and the 49-transparency set above
give a far more compact (yet also quite nice)
presentation, and do not attempt to cover the section on
associative one-way functions.
- A set of 26 transparencies (written in 2001):
As
powerpoint source.
Note: This 26-transparency set covers (quite nicely)
pretty much the entire chapter,
including even coverage of associative one-way functions, but is
of course not as detailed a treatment as is given in the 102-transparency
set above.
- Transparency set for Chapter
3, The Tournament Divide and Conquer Technique.
- An set of 75 transparencies (written in 2015):
As
powerpoint source and as a
pdf export.
- A set of 65 transparencies (written in 2006):
As
pdf.
Note: Slide 8 silently assumes that the coding of TM programs is
prefix-free (which in the textbook is not assumed).
Without that strong assumption, Chaitin's constant
might be infinite which would destroy the theorem.
- A set of 95 transparencies (written in 2004):
As
a pdf export
and as
powerpoint source.
(Warning: In the pdf version, the \emptyset and \in characters
come out wrong in some readers---see the warning on transparency 2.)
- Transparency set for Chapter
4, The Isolation Technique.
- Transparency set for Chapter
5, The Witness Reduction Technique.
- A set of 79 transparencies (written in 2006):
As
pdf.
- A set of 34 transparencies (written in 2001):
This one is a bit tricky. The talk is a 20-transparency powerpoint
presentation, but at transparency 9, which says "Handwritten slides here
for Theorem 5.5," one must go the a set of 14 handwritten transparencies
(which are below as a tar of 14 tiff files, named s1, s2, ..., s14).
So, the powerpoint
portion is
here as powerpoint source
and the handwritten transparencies are in
this very, very large "tar" archive containing 14 tiff image
files (which can be viewed with an appropriate viewer, such as xv).
- Transparency set for Chapter
6, The Polynomial Interpolation Technique.
- A set of 38 transparencies (written in 2001):
As
powerpoint source.
Note: These transparencies mostly focus on
arithmetization.
- Transparency set for Chapter
7, The Nonsolvable Group Technique.
- A set of 38 transparencies (written in 2001):
As
a postscript export
and (in case you live in the apple world and can figure out how
to extract and use this) as
source code in the form of an email message
that has some type of very kinky apple format file buried in it under
a level of mime-encoding.
(Warning: Regarding the postscript version,
the transparencies orient ok in ghostview, but under GSview you'll have
to use Media->RotateMedia to avoid having the previewer truncate all
the transparencies due to it confusing which dimension is which.)
Click here
to return to top of the current page.
Click here
to return to the web
home page of The Complexity
Theory Companion.