Monday, June 09, 2003

Howdy from San Diego

›
This week I'm at the Federated Computing Research Conference (FCRC), a combination of thirty conferences and workshops with 2200 parti...
Friday, June 06, 2003

Back to Chicago

›
A personal note: I have accepted an offer to return to the computer science department of the University of Chicago starting this fall. As...
Tuesday, June 03, 2003

Foundations of Complexity
Lesson 19: The Immerman-Szelepcsenyi Theorem

›
Previous Lesson In this lesson we will prove the Immerman-Szelepcsényi Theorem. Theorem (Immerman-Szelepcsényi): For reasonable s(n...
8 comments:
Wednesday, May 28, 2003

Open Questions from Hopcroft and Ullman

›
On page 281 of the 1979 edition the classic theory text of Hopcroft and Ullman lies two tables describing closure and decidability propert...
Thursday, May 22, 2003

Computing's Lost Allure?

›
The New York Times today had an article on the shrinking number of computer science majors in American universities. Let me give you my t...
Wednesday, May 21, 2003

Celebration for Walter Savitch

›
Just got this announcement. And we just discussed Savitch's Theorem in my last Foundations Lesson . The Department of Computer Scienc...
Friday, May 16, 2003

Turing Machines and Godel's Theorems

›
A little recursion theory can make Gödel's Theorems intuitively easy. Let A be the set of <M> such that M does not accept the i...
Wednesday, May 14, 2003

Foundations of Complexity
Lesson 18: Savitch's Theorem

›
Previous Lesson | Next Lesson Unlike what we believe for time, there is a polynomial relation between deterministic and nondeterminis...
Monday, May 12, 2003

The Nerd Shot

›
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 ...
Thursday, May 08, 2003

Foundations of Complexity
Lesson 17: Space Complexity

›
Previous Lesson | Next Lesson In addition to time, computer scientists also worry about the memory or space that a Turing machine u...
Tuesday, May 06, 2003

Universal Search

›
Psst. Want to know the fastest algorithm for factoring? I can give you an algorithm that is within a constant multiplicative factor of the ...
Sunday, May 04, 2003

FCRC

›
Even the largest theoretical computer science conferences draw at most a couple of hundred people. Many (but not all) other areas of comput...
Thursday, May 01, 2003

History's Loss/Mathematics' Gain

›
Some excitement at Schloss Dagstuhl this week. Localized high winds tore the metal plating off the roof of much of the new building Wednesda...
Wednesday, April 30, 2003

The Power of Random Strings

›
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 ...
Tuesday, April 29, 2003

More on Kolmogorov Complexity

›
There is a great Dilbert cartoon explaining the need for Kolmogorov complexity. Because of copyright issues, I won't put it here (but y...
Sunday, April 27, 2003

Kolmogorov Centennial

›
Andrei Kolmogorov was born exactly hundred years ago last Friday the 25th. Kolmogorov made major contributions to "every mathematical ...
Wednesday, April 23, 2003

Complexity Classes of the Week: SBP and A0PP

›
Previous CCW Two new complexity classes developed independently for two different purposes with eerily similar definitions. Let's tak...
Tuesday, April 22, 2003

Paddable NP-Complete Sets are Isomorphic

›
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 ...
Friday, April 18, 2003

The Turing Award

›
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 . Unfort...
Tuesday, April 15, 2003

Awards

›
The ACM doctoral dissertation award , given to the best doctoral thesis in computer science, was awarded to Venkatesan Guruswami for his...