Computational Complexity

I'd like to remember two young people who's lives were taken way too early. I didn't know either well but both played large r...

(This post is inspired by the choice of a female to be the next Doctor on the TV show Dr. Who. Note that you can't say `the next Dr. Who...

Whenever I teach discrete math and use FML to mean Formula the students laugh since its a common acroynm for  Fuck My Life. Now they laugh, ...

On Nate Silver's page he sometimes (might be once a week) has a column edited by Oliver Roeder of problems. Pretty much math problems th...

It's Monday as I write this post from home. Atlanta, for the first time ever, is in a tropical storm warning. Georgia Tech is closed tod...

In 2009 I had a post about Movie mistakes (see here ). One of them was the Scarecrow in The Wizard of Oz after he got a Diploma (AH- but not...

When I teach a small (at most 40) students I often have the dead-cat policy for late HW: HW is due on Tuesday. But there may be things tha...

As a mathematician nothing grates me more than the expression "The exception that proves the rule". Either we bake the exception i...

Note: Thanks to Sasho and Badih Ghazi for pointing out that I had misread the Tardos paper. Approximating the Shannon graph capacity is an o...

Someone has published three papers claiming that π is 17 -8*sqrt(3) which is really =3.1435935394... Someone else has published eight p...

Stuart Kurtz turned 60 last October and his former students John Rogers and Stephen Fenner organized a celebration in his honor earlier th...

A joint post from Lance and Bill This blog started fifteen years ago today as  "My Computational Complexity Web Log". Bill came...

(Thanks to Rachel Folowoshele for bringing this to my attention) John Urschel is a grad student in applied math at MIT. His webpage is  he...

Remember the Bluetooth craze where it seemed half of all people walked around with a headset in their ear. Now you rarely do. Remember Goo...

Phillip Rogaway's article on the The Moral character of Cryptographic Work (see  here ) brings up so many issues that it could be th...

Too often we see bad definitions, a convoluted mess carefully crafted to make a theorem true. A student asked me though what makes for a gre...

Over at  the blog Bits and Pieces my adviser Harry Lewis (is he still my adviser 32 years after I got my PhD? Yes) has written many posts a...

Peter Wegner passed away yesterday morning at the age of 84. As a child he escaped Stalinist Russia and Nazi-occupied Austria  the latter...

For the last two weeks, the wife and I took a vacation to beautiful Norway to see the fjords and the North Cape, effectively the northernmos...

What are the top Computer Science Programs for Women? How would one even answer the question? Some people did a study based on National ...