Computational Complexity

What does the complexity world look like if we have hard functions that let us efficiently derandomize? All of the results in this post foll...

In the back of my high school Biology book had a big circle with many smaller circles and I clearly made out the word "color". Tha...

In the ancient days of the early '80s when you wanted a copy of a research paper and didn't have it in your library, you sent a stam...

A German student came up to me during the Complexity conference last week. "The Czechs beat the US in the World Cup" That game ha...

June Edition The permanent of a matrix has a simple form Perm(A)=Σ σ a 1&sigma(1) a 2&sigma(2) ···a n&sigma(n) where A i...

Amir Michail writes I was wondering if you might comment on the history behind the formation of computer science, and in particular, on the...

Today I fly back to Chicago ending my three country European tour. During this Complexity Conference I stepped down from my role as chair of...

The Complexity Conference got underway yesterday with an invited talk by Pavel Pudlak on the connections of Gödel's work and computatio...

I have arrived in Prague for the Conference on Computational Complexity , my favorite conference as you might guess from the name of the we...

Peter Wegner and Dina Goldin are at it again . The following is from their Viewpoint article Principles of Problem Solving in the July CACM...

Those who know me well know my addiction to junk food, often referred to as "Lance Food" during my graduate school days. America h...

In our sixth Complexitycast live from Portugal, Luis Antunes talks about the Portugal view of theory, research and of course the World Cup....

How do complexity classes get named? A proposal gets submitted to the Complexity Class Naming Commission (CCNC) which makes sure the class w...

When Karp and Lipton showed that if NP had polynomial-size circuits the polynomial-time hierarchy collapses, they also give a general defin...

At noon today, as I was checking into my flight to Porto, Heathrow Airport went quiet, part of a nationwide two-minute memorial for the Lond...

The Complexity and Randomness workshop in Bristol has an unusual mix of researchers in random graphs and mixing (the British) and complexit...

I have just started a three week European trip. This week at the Randomness and Complexity workshop in Bristol, next week in Porto, Portuga...

I have just started a three week European trip. This week at the Randomness and Complexity workshop in Bristol, next week in Porto, Portuga...

New superhero movies like Superman Returns and X-Men: The Last Stand remind me of my one time comic book addiction. As a child, I liked to...

The list of accepted papers for FOCS 2006 has been posted. Since I was on the program committee I won't comment on the papers or the p...