Glencora Borradaile

         Associate Professor & College of Engineering Dean's Professor, School of Electrical Engineering and Computer Science, Oregon State University

March 17, 2012

crash course in TCS

Filed under: Silent Glen Speaks @ 8:20 pm
Tags: ,

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


  1.   JK — March 18, 2012 @ 1:12 am    

    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.   Omer Reingold — March 18, 2012 @ 4:12 am    

    It is great that you are spreading the word about TOC. You may be interested in a general audience talk I gave a few years ago:

    •   Glencora Borradaile — March 21, 2012 @ 8:56 pm    

      Thanks for the link!

  3.   Daniil — March 19, 2012 @ 7:35 pm    

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

    •   Glencora Borradaile — March 21, 2012 @ 8:55 pm    

      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.

RSS feed for comments on this post.

Sorry, the comment form is closed at this time.

© 2018 Glencora Borradaile   Powered by WordPress MU    Hosted by