The list of accepted papers of STOC has been posted. STOC and FOCS are the two most important annual theoretical computer science conferences. Quite a few...
For those with access to the Journal of the ACM , the fiftieth anniversary issue (Volume 50, Number 1) has a number of very short articles by prominent...
Daniel Varga asks about the question of NEXP not in P/poly and whether it is "fundamentally" easier than NP not in P/poly. As a reminder: NEXP is the class of...
Previous Lesson Now that we have shown that CNF-SAT is NP-complete we can use it to show many other problems are NP-complete via the following lemma. Lemma: If...
Yesterday's post on NP-complete problems reminds me of one of the more interesting open questions, the complexity of the traveling salesman problem on the ...
I noticed that Slashdot has recently mentioned some TCS research. This would therefore be theoretical computer science that matters to nerds. The first was a...
Previous CCW Let us call a nondeterministic Turing machine M balanced if for every input x, all of its computational paths have the same length, i.e., the...
Today I saw Maria Chudnovsky give a talk at Princeton on her new result with Paul Seymour finding a polynomial-time algorithm for testing perfect graphs, a...
The list of accepted papers for the 18th Annual IEEE Conference on Computational Complexity is now available. The conference will be held July 7-10 in rhus,...
Russell Impagliazzo and Phillipe Moser have an upcoming Complexity paper entitled A Zero-One Law for RP . What does that mean? Jack Lutz defined a notion of...
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...
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.
