Computational Complexity

A reader asks I wanted to ask you something about the Savitch and Immerman-Szelepcsényi theorems that I saw you have in your weblog. In...

Mike O'Donnell tells a story of talk he saw once where the speaker considered the following recursive program: f(n) := output 0 if n =...

Using performance-enhancing drugs has become a major issue in national and international sports, most recently in Major League Baseball in A...

I have a brother who worked in the music industry and got us first row tickets to Kool and the Gang. I have a brother who was an entertainme...

A few years ago someone asked Steven Rudich, a complexity theorist at Carnegie-Mellon, why he thought P is different than NP. He replied ...

From Chris Bourke : I've created a LaTeX package for typesetting complexity commands ($\P$, $\NP$, etc). Its available on CTAN . Not on...

Given a k-tape Turing machine can we reduce the number of tapes without too large an increase in time and space (memory)? Not just an esoter...

My father passed away 25 years ago today. I thought I would share some of the lessons I learned from him. Once you win an argument, stop ar...

In 2005 I have already traveled on five trips to four different countries on three different continents. My travel comes in bunches. I didn...

When I visit Amsterdam I rent a bike for much the same reason I rent a car when I travel to New Jersey. CWI is in the east part of the city ...

This week I visit CWI in Amsterdam where I spent my sabbatical year eight years ago and continue working relationships with many people her...

The Tamagotchi craze has hit my daughters' school. The Tamagotchi is a small toy with a few buttons and a screen where you can play wit...

Scott Aaronson has a fun paper in the complexity column of the new SIGACT News where he addresses the question: Can NP-complete problems be...

February Edition How do we formalize the notion of efficient computation? Two important papers from the 60's suggest polynomial time a...

I finally read Clayton's Christensen's The Innovator's Dilemma . A few years ago an NEC executive gave a talk using the ideas in...

Here is an interesting problem given by Muthukrishnan during his talk in the New Horizons workshop. Start with an array A of n+1 entries ea...

Japan has produced some excellent theorists, like Seinosuke Toda who won the 1998 Gödel prize for his paper reducing the polynomial-time h...

Two fellow (and slightly better known) Chicago professors Gary Becker and Richard Posner run a joint weblog on various social issues. This ...

I'm off to Japan for a Workshop on New Horizons in Computing that kicks off a new theory project sponsored by the Japanese Ministry of...

Below the paid ads, Gmail gives me related links on the side of my email. In a discussion on a bad P ≠ NP proof (don't ask) Gmail pointe...