Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] Topics for theory grad course for non theorists?

Expand Messages
  • GASARCH
    (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
    Message 1 of 1 , Jul 17, 2008
    View Source
    • 0 Attachment
      (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:
      1. Impossibility of distributed consensus with faults
      2. von Neumann minimax theorem
      3. 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
    Your message has been successfully submitted and would be delivered to recipients shortly.