crash course in TCS

I recently gave a pair of talks in the Math Department’s Applied Math Seminar on basics of TCS.  It was intended for a mathematically mature audience with no background in TCS.  The slides for the talk are available here; they are far from perfect — but I will happily take suggestions on things that should be dropped or added.  Interest in the talk was pleasantly high.  High enough that I plan on doing this again and advertising more broadly — to graduate students in physics, engineering, etc.  I also think it acts as a list of topics about which students should be able to answer questions during a comprehensive exam.

Hint.  Hint.

Print Friendly, PDF & Email

5 thoughts on “crash course in TCS

  1. JK

    You could, of course, mention cryptography. (If complexity is about the limits of computation, and algorithms involves working within those limits, then cryptography exploits those limits for beneficial use.)

  2. Daniil

    What about stuff like computational logic and automata theory? Do you not consider it TCS?

    1. Glencora Borradaile Post author

      Given the time limit (< 2hr), I did not attempt to be complete. However, I would be interested to know what you take out in order to add something else.

Comments are closed.