I have just started a three week European trip. This week at the Randomness and Complexity workshop in Bristol, next week in Porto, Portugal and ending up at...
I have just started a three week European trip. This week at the Randomness and Complexity workshop in Bristol, next week in Porto, Portugal and ending up at...
The Complexity and Randomness workshop in Bristol has an unusual mix of researchers in random graphs and mixing (the British) and complexity (the rest of us). ...
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 London bombing victims...
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 London bombing victims...
When Karp and Lipton showed that if NP had polynomial-size circuits the polynomial-time hierarchy collapses, they also give a general definition of nonuniform...
How do complexity classes get named? A proposal gets submitted to the Complexity Class Naming Commission (CCNC) which makes sure the class was not already...
In our sixth Complexitycast live from Portugal, Luis Antunes talks about the Portugal view of theory, research and of course the World Cup. MP3 (13:26, 2.3MB)...
Those who know me well know my addiction to junk food, often referred to as "Lance Food" during my graduate school days. America has its great variety of such...
Peter Wegner and Dina Goldin are at it again . The following is from their Viewpoint article Principles of Problem Solving in the July CACM. Theoretical...
I have arrived in Prague for the Conference on Computational Complexity , my favorite conference as you might guess from the name of the weblog. STOC and FOCS...
The Complexity Conference got underway yesterday with an invited talk by Pavel Pudlak on the connections of Gdel's work and computational complexity. Kurt Gdel...
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 conference...
Amir Michail writes I was wondering if you might comment on the history behind the formation of computer science, and in particular, on the subsequent ...
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 is an nn matrix, a ij is the element in the ...
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 is an nn matrix, a ij is the element in the ...
A German student came up to me during the Complexity conference last week. "The Czechs beat the US in the World Cup" That game happened a month before. "And...
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 stamped self-addressed envelope...
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". That was easy I thought until I...
What does the complexity world look like if we have hard functions that let us efficiently derandomize? All of the results in this post follow from the...
I have used Gmail extensively as my main email system for a couple of years now. I often get asked about letting Google have access to all my email. Is my...
The winners of the 2006 Fulkerson Prize have been announced. The Fulkerson prize is given every three years to up to three papers in discrete mathematics. ...
Victor has tried and failed to solve the latest Sudoku game and exclaims no solutions exists. His wife Paula has already solved the game. How does Paula...
When looking for a long-term partner, you may have had a long string of failed dates, but you must remain optimistic that the next one will be "the one." You...
Will we ever have useful quantum computers? Despite the "breakthroughs" we seem to have nearly every month, we are a long way off from controlling even a...
Eldar Fischer reports from Haifa. Truth be told, the beginning of the missile season was a surprise for us all. It is true that enough people can claim to have...
The prediction market exchange Tradesports have themselves a little controversy over North Korean missiles. I have written about prediction (or information...
Next week I am on vacation and off the Internet. Claire Kenyon will be your guest blogger. I get to experience the new airline rules, no water, toothpaste,...
Thanks to Claire for guest blogging during my vacation. I apologize for the various technical difficulties on the weblog last week and all should be better...
The editorial board of the Elsevier journal Topology have followed the lead of the editors of the Journal of Algorithms and have resigned effective the end of...
Having problems with message search?
Fill out this form to ensure your group is one of the first to be migrated to the new message search system.
