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...
Even the largest theoretical computer science conferences draw at most a couple of hundred people. Many (but not all) other areas of computer science also do...
Psst. Want to know the fastest algorithm for factoring? I can give you an algorithm that is within a constant multiplicative factor of the best possible...
Previous Lesson In addition to time, computer scientists also worry about the memory or space that a Turing machine uses. Roughly one can measure space as the...
Many years ago I was commuting home on the train with my wife and one of her colleagues. I showed them the group picture from a Dagstuhl I had attended that...
Previous Lesson Unlike what we believe for time, there is a polynomial relation between deterministic and nondeterministic space. Savitch's Theorem (1970): ...
A little recursion theory can make Gdel's Theorems intuitively easy. Let A be the set of <M> such that M does not accept the input <M>. By diagonalization...
Just got this announcement. And we just discussed Savitch's Theorem in my last Foundations Lesson . The Department of Computer Science and Engineering at the...
The New York Times today had an article on the shrinking number of computer science majors in American universities. Let me give you my take on this. First of...
On page 281 of the 1979 edition the classic theory text of Hopcroft and Ullman lies two tables describing closure and decidability properties of various formal...
A personal note: I have accepted an offer to return to the computer science department of the University of Chicago starting this fall. As NEC Labs has been...
This week I'm at the Federated Computing Research Conference (FCRC), a combination of thirty conferences and workshops with 2200 participants. I'm here for the...
Last night was the business meeting for STOC. This used to be a raucous affair with major battles over issues like whether to have parallel sessions, but now...
Last night was the business meeting for STOC. This used to be a raucous affair with major battles over issues like whether to have parallel sessions, but now...
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.
