Last weekend the movie Enemy of the State was shown on network television in the US. This is a pretty good thriller about a rouge NSA official using the...
Breaking news on a post from last October. The US Supreme Court ruled in favor of Disney that ever increasingly long finite lengths of copyright protection...
Prevous Lesson We will show that CNF-SAT is NP-complete . Let A be a language in NP accepted by a nondeterministic Turing machine M. Fix an input x. We will...
Last night I (and forty other complexity theorists) received by email an anonymous paper entitled "NP = coNP". After a quick scan it was clear there was not...
Just in case you thought computer scientists only deal with computers, here is a New York Times article describing how AT&T researcher Matt Blaze using tools...
One cannot celebrate Alonzo Church, part of our Celebration of Geniuses without talking about his creation, the Lambda Calculus, a way to describe functions...
Last year we saw the resolution of the Strong Perfect Graph Conjecture, a major result in graph theory . The conjecture stated that a graph is perfect if and...
Next week I will go away on vacation. When I go on a real vacation I go cold turkey on the Internet. No new posts or responses to comments or email until I...
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 ...
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.
