Computational Complexity

There is now a I can be an engineer Barbie. That sounds good! It's not. Imagine how this could be turned around and made sexist. What y...

The Imitation Game  starring Benedict Cumberbatch as Alan Turing opens in the US on November 28. If you read this blog you should see that m...

I was recently in Boston for Mikefest (which Lance talked about  here)   and found time to talk to  my adviser Harry Lewis at Harvard (advi...

Inspired by the Dantzig Story   I occasionally put an open problem on a class assignment. Never worked, though I did have a student get a re...

US News has a ranking of CS depts and various subcategories. Recently MohammadTaghi Hajiaghay and Luca Trevisan have suggested alternative r...

We celebrate the 100th anniversary of the birth of George Dantzig today. In his obituary post  we talked about his work on optimization, par...

My long time blog readers should have no surprise on my final favorite theorem of 2005-2014. Nonuniform ACC Circuit Lower Bounds by Ryan ...

While Lance was AT Mikefest (Sipser's 60th Bday conference), helping to organize it, emceeing the personal statements, I was... also th...

Congratulations to the San Francisco Giants, winning the World Series last night. In honor of their victory let's talk metrics. Baseball...

On Sunday we had the Symposium on Theoretical Computer Science on the Occasion of Michael Sipser's 60th birthday to celebrate what M...

(This is a guest post by MohammadTaghi Hajiaghayi. His name is not a typo- the first name really is MohammadTaghi.) Due to our belief in t...

The Committee for the Advancement of Theoretical Computer Science put together an open letter to several research leaders at Microsoft. We...

Martin Gardner was born on October 21, 1914, so today is his Centennial (he died on May 22, 2010, at the age of 95). We've mentioned him...

NP (nondeterministic polynomial time) and NEXP (nondeterministic exponential time) are provably different classes by the nondeterministic ti...

My first ever guest post for Lance was on Are you a luddite . I certainly am to some extent a luddite, but there are some things where it no...

Tis the season for the fall jobs post. Please list any jobs, academic or industrial, in theoretical computer science broadly construed in th...

Recall 1-pile NIM: Let A be a finite set of Naturals. NIM(A) is the following game: There are n stones on the board. Players I and II alte...

In the past decade we have seen a strong program in algebraic circuit complexity. If you just define circuits using multiplication and addit...

(Reminder- Theory day at UMCP:  here is the link. ) There was a Dagstuhl on Algebra in Computational Complexity Sept 22-26. I learned st...

I rarely highlight individual events on the blog, but one's advisor only turns sixty once. We will honor Michael Sipser  at MIT on Sund...