Category Archives: Landscape

Greatest Hits of TCS: SL=L

Alright!  As promised, here’s the first of the Greatest Hits of TCS. To kick it off, Prasad Raghavendra presented Omer Reingold’s celebrated result of SL=L.  Prasad not only gave a beautiful tour through the work and threw some great perspectives … Continue reading

Posted in Advanced, Humanity, Landscape, TCS | Tagged , , , , , , , , | Leave a comment

Greatest Hits of TCS (or This Really IS a TCS Blog, I Swear!)

This semester Prasad Raghavendra is holding a course called Theoretical Computer Science’s Greatest Hits.  It seems like it’s going to be a lot of fun! Anywho, I thought I’d keep you folks all up to date and give a synopsis … Continue reading

Posted in Intermediate, Landscape, TCS | Tagged , , , | 1 Comment

Well, Obviously…

So there was a math professor lecturing to their class.  The class had just started but they were already getting into some heavy-duty stuff. No more than five minutes into the class, some smart-ass pipes up, interrupting the professor’s unfurling … Continue reading

Posted in Humanity, Landscape, Pedagogy | Tagged , , , , | Leave a comment

A Circuitous Parable

Last week I accidentally built a bookcase that didn’t fit my bed.   Obviously, that sentence doesn’t make sense.  Do you know what else doesn’t make much sense?  Research. Actually, research does make sense.  In fact, it makes perfect sense … Continue reading

Posted in Humanity, Intermediate, Landscape, TCS | Tagged , , , , | Leave a comment

A Roll In The Hay

Haystacks.  Haystacks, everywhere. Let’s get something straight, all algorithms are exhaustive search.  We just need to find the right haystack. In a previous post I talked about complexity theory getting off to a bizarre, albeit beautiful, start that ended us … Continue reading

Posted in Intermediate, Landscape, TCS | Tagged , , , , | Leave a comment

Cold Off The Press!

Big news!  It looks like Laci Babai has a quasipolynomial time algorithm for Graph Isomorphism (GI). That is, GI has jumped from the best known algorithm being almost exponential, to being almost polynomial! But, of course, you probably already heard … Continue reading

Posted in Beginner, Community, Landscape, News, TCS | Tagged , , | Leave a comment

Alphabet Soup

Computational complexity theory is math putting us mere mortals in our place. Complexity theory got off to a bizarre, albeit beautiful, start.  Birthing from Hilbert’s majestic notion that, for mathematics, there is no ignorabimus, the race was on. The race … Continue reading

Posted in Beginner, Humanity, Landscape, TCS | Tagged , , | Leave a comment