Computational Complexity

Goro Hasegawa passed away last week at the age of 83. Hasegawa created and popularized the board game Othello based on an old British game ...

Lance : Bill, there is a new result on cake cutting that was presented at STOC! Do you want to blog about it? Bill: Do snakes have hips! ...

I attended the 2016 STOC Conference earlier this week in Cambridge, Massachusetts. No shortage of awesome results highlighted by László Ba...

In my last post  When does n divide a_n?  I gave a sequence: a(1)=0 a(2)=2 a(3)=3 for all n ≥ 4 a(n) = a(n-2) + a(n-3) and I noted...

Avi Wigderson responds to yesterday's post . 20 years is a long time, and TCS is in a completely different place today than it was the...

The 48th ACM Symposium on the Theory of Computing  starts this weekend in Boston. Let's go back twenty years to the 28th STOC, part of t...

Consider the following sequence: a(1)=0 a(2)=2 a(3)=3 for all n ≥ 4  a(n) = a(n-2)+a(n-3) Here is a table of a(n) for 2 ≤ n ≤ 23 ...

In 1997  Good Will Hunting , a fictional movie about the hidden mathematical talents of a MIT janitor grossed $225 million and won a best sc...

(This post is based on articles from 2012 so it may no longer be true. Also- to be fair- I tried finding stuff on the web BY the people who ...

Earlier this week I attended the 31st Computational Complexity Conference in Tokyo. I've been to thirty of these meetings, missing only...

If you finitely color the natural numbers there will be a monochromatic solution to x+2y+3z - 5w = 0 There is a finite coloring of the ...

In the fall we point to theory jobs , in the spring we see who got them. How is the CS enrollment explosion affecting the theory job market?...

(Workshop for women in computational topology in August:  see here . For a post about these kinds of workshops see  here .) (I have alrea...

The US television industry has long fascinated me, an entertainment outlet driven by technology. David Sarnoff introduced television at the ...

Here are four fictional stories though inspired by real world events or TV shows (I forget which is which). My question is, was a confidence...

Earlier this week I attended the CCC workshop  Computing Research: Addressing National Priorities and Societal Needs  ( video ). The worksho...

There may be articles titled Donald Trump and the Failure of Democracy. This is NOT one of them. This is about some math questions. I drew u...

Through the years I've mentioned a few of my favorite open problems in computational complexity on this blog that have perplexed me thro...

I posted about the Gathering for Gardner conference and about some of the talks I saw  here.  Today I continue with a few more talks. Pla...

Claude Shannon was born hundred years ago Saturday. Shannon had an incredible career but we know him best for his 1948 paper A Mathematica...