
Recent Posts
Archives
Categories
 BubbleBreaking (2)
 Community (3)
 Grad School (7)
 Survival Tips (1)
 Humanity (13)
 Landscape (7)
 News (4)
 Pedagogy (1)
 Social Topic (4)
 TCS (6)
 Advanced (1)
 Beginner (2)
 Intermediate (3)
Recent Comments
OK…So, What Do… on Two Horses’ Asses Greatest Hits of TCS… on To A Beginning Greatest Hits of TCS… on Greatest Hits of TCS (or This… Manuel Sabin on Bowie In Berkeley Manuel Sabin on Bowie In Berkeley Tags
 Baobabs
 Beginning
 Breakthrough
 Bukowski
 Complexity Theory
 Context
 Courses
 David Bowie
 Decision
 Derandomization
 Exhaustion
 Exhaustive Search
 Expanders
 Fear
 FNP
 Gender
 Graph Isomorphism
 Haystacks
 Inequality
 Insecurities
 Lazlo Babai
 Logic
 Math Muses
 Modest Mouse
 Notation
 Omer Reingold
 Platonism
 Prasad Raghavendra
 Pursuit
 Race
 Responsibility
 Russell Impagliazzo
 Ryan Williams
 Search
 Simons
 Space Complexity
 TCS's Greatest Hits
 Trump
 ZigZag Product
Meta
 Follow On The Shoulders Of Windmills on WordPress.com
Category Archives: TCS
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 Context, Courses, Prasad Raghavendra, TCS's Greatest Hits
1 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 Complexity Theory, Context, Pursuit, Ryan Williams, Simons
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 Decision, Exhaustive Search, FNP, Haystacks, Search
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 Breakthrough, Graph Isomorphism, Lazlo Babai
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 Complexity Theory, Logic, Notation
Leave a comment