(Guest Post by Kirk Pruhs.)
I am taking over teaching our graduate CS theory course.
I will be teaching to PhD students who will not become theoreticians.
I want to emphasize concepts and broad knowledge,
not formal proofs or training students to do formal proofs.
The plan for most classes is to get the students to understand
the statement of one theorem, and the significance of that theorem,
with the remaining time devoted to some intuitive explanation
of why the theorem is true. I want the the course to be at least a little
bit broader than a standard complexity class. For example, possible
topics that are not standard complexity topics:

Impossibility of distributed consensus with faults

von Neumann minimax theorem

no minimum energy for computation
I would like to solicit suggestions as to what theorems and
topics
one should teach to CS PhD students who will not become theoreticians.
I probably will have time to 25 to 30 topics.

Posted By GASARCH to
Computational Complexity at 7/17/2008 08:43:00 AM