[Computational Complexity] Topics for theory grad course for non theorists?
- (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
Posted By GASARCH to Computational Complexity at 7/17/2008 08:43:00 AM