John Tromp at CWI has been telling me about some work he is doing on the Rush Hour problem. Rush Hour is a puzzle where you have to remove a car stuck in...
I posted the slides of my talk, "Church, Kolmogorov and von Neumann: Their Legacy Lives in Complexity" that I presented at the Dutch Theory Day last week, for...
Four speakers are chosen for the NVTI Theory Day along two axis: In and out of the Netherlands, and Theory A and Theory B. For example I was the non-Dutch...
Previous CCW Let A={a ij } be an nn matrix over the integers. The determinant of the A is defined as Det(A)= (-1) || a 1(1) a 2(2) ...a n(n) where ranges over...
In yesterday's post I linked to some lecture notes of Vigoda on Valiant's result. Those notes also cite a paper of Zank. Now every paper has a story but this...
Check out America's Favorite Binary Tree . -- Posted by Lance Fortnow to My Computational Complexity Web Log at 3/16/2003 7:59:43 PM Powered by Blogger Pro...
I was teaching my class right after the first Gulf war started in 1991 and wondering what to say. Sometimes I wish I were a history or government professor and...
On Sunday, I posted a link to the 2003 NCAA Division 1 Men's Basketball Championship Brackets which I called "America's Favorite Binary Tree". But in a strange...
Suppose you want to make a prediction on say who will win the Best Actress Award at Sunday's Oscars. You can visit various web sites, look at the predictions...
The accepted papers for ICALP have been posted. As I mentioned last week, ICALP has two submission tracks that match the Theory A and Theory B split. The list...
Some follow up on earlier posts of this week. The University of Connecticut defeated BYU in men's basketball yesterday, keeping the integrity of the tree . If...
Previous Lesson In the 1950's, Friedberg and Muchnik independently showed that there were sets that were computably enumerable, not computable and not ...
Haipeng Guo asks "Is is possible that the P vs NP problem is undecidable? Is there any paper talking about this?" Short Answer: Until we have a proof that PNP...
In 1976, Berman and Hartmanis considered whether all of the NP-complete problems might be the same. We says sets A and B are polynomial-time isomorphic if...
There has been a really amazing development today on Fermat's Last Theorem. Noam Elkies has announced a counterexample, so that FLT is not true after all! His...
"The Institute" in yesterday's post refers to the The Institute for Advanced Study , a fully-endowed facility devoted to fundamental research. WNET, the New...
My post on Fermat's last theorem last week reminded me of my personal all-time favorite math parody, a Chicago Tribune column written by Eric Zorn. Zorn,...
In the April issue of the Communications of the ACM, Peter Wegner and Dina Goldin have a technical opinion entitled Computation Beyond Turing Machines . From...
Because of the popularity of the war weblogs, the Haloscan commenting system I was using was being overloaded which would on occasion cause my web log to have...
In the old commenting system, Daniel Varga had the following comment on my post on unprovability . I guess Alexander Razborov turned to the study of...
A couple of interesting pieces in the New York TImes. Jim Holt reviews George Johnson's A Shortcut Through Time: The Path to a Quantum Computer . I haven't...
Often graduate students ask me for a good problem to work on. This is one of the biggest challenges of an advisor. A good problem for a graduate student must...
The ACM doctoral dissertation award , given to the best doctoral thesis in computer science, was awarded to Venkatesan Guruswami for his thesis "List-Decoding...
As noted in a comment to the last post, it is now official that Ron Rivest, Adi Shamir and Len Adleman won the 2002 Turing Award . Unfortunately outside of...
By request, here is a sketch of the proof of the Berman-Hartmanis 1978 result that all paddable NP-complete sets are isomorphic. The proof is builds on an old...
Previous CCW Two new complexity classes developed independently for two different purposes with eerily similar definitions. Let's take a look. Bhler, Glaer and...
Andrei Kolmogorov was born exactly hundred years ago last Friday the 25th. Kolmogorov made major contributions to "every mathematical area except number...
There is a great Dilbert cartoon explaining the need for Kolmogorov complexity. Because of copyright issues, I won't put it here (but you might find it at the...
Let R be the set of random strings, the x such that C(x)|x|. There are various theorems that many such x must exist at every length. What is the power of R? R...
Some excitement at Schloss Dagstuhl this week. Localized high winds tore the metal plating off the roof of much of the new building Wednesday evening. Much of...
