The Annotated Turing: A Guided Tour Through Alan Turing’s Historic Paper on Computability and the Turing Machine by Charles Petzold
P.S. Charles has a blog, and some recent post are about Turing and this book.
In an Intel Software Network article titled Parallel computing: disappearing from CS curricula???, Michael Wrinn demonstrated that parallel computing has gradually disappeared from popular CS curricula in the past 10+ years. His first example is:
[...] a panelist at IPDPS (in Miami, a couple of weeks ago) assert that parallel-processing topics have been disappearing from CS curricula in recent years. As anecdotal evidence, he pointed out the topic’s removal in the 2nd edition of Introduction to Algorithms [...]
The article goes on to give several other examples to prove his point. In the end, Michael wrote
[...] multicore computing platforms are now the norm. Recognizing that reality, let’s make the adjustment time short.
Are we expecting a surge of algorithm and data structure textbooks with an emphasis in multicore? 
25
Apr
Available here at informIT.
Andrew Binstock and Donald Knuth converse on the success of open source, the problem with multicore architecture, the disappointing lack of interest in literate programming, the menace of reusable code, and that urban legend about winning a programming contest with a single compilation.
Among other things, he explained why the numbering of Volume 4 fascicles starts at 0 and not 1. (You may recall that there is no Volume 0 and so zero-based counting cannot be exactly the reason. Well, I mean not exactly.)
From this New York Times article:
Algorithms, as closely guarded as state secrets, buy and sell stocks and mortgage-backed securities, sometimes with a dispassionate zeal that crashes markets. Algorithms promise to find the news that fits you, and even your perfect mate.
Perfect!
See this great post in Michael Trick’s OR Blog on a recent article in the Economist magazine titled “Business by numbers”.
Among other things, this is how the Economist article begins:
Algorithms sound scary, of interest only to dome-headed mathematicians.
Well, I have no idea what “dome-headed” means, but Google tells me that dome-headed creatures can be scary. Now, domed-head mathematicians… hmm, maybe it has to do with banging the head to the wall?
15
May
http://www.eatcs.org/activities/awards/goedel2007.html
The 2007 Gödel Prize for outstanding journal articles in theoretical computer science is awarded to:
Alexander A. Razborov and Steven Rudichfor their paper
“Natural Proofs”, Journal of Computer and System Sciences, Vol. 55, No. 1, 1997, pp. 24-35.It was first presented at the Twenty-sixth Annual ACM Symposium on Theory of computing, Montreal, Quebec, Canada. 1994, pp. 204 – 213.
I note that Natural Proofs have been written a couple times before on the blogosphere, and I further note that the prize must have been announced at least a week ago from seeing a link into the latter post. Ha!
Posted here:
http://www.cs.colorado.edu/~hal/alist.txt
Update: Some stats are available in this post in Geomblog.
If you have not registered for FOCS 2005 yet, please consider doing it now. The early registration for the conference and also the hotel is ending this Friday (Sept 23).
Well, I don’t know if SODA is rising, falling, or maybe falling in one regard because it is rising in another, but I do know that the list of accepted papers has been published.
According to Cliff Stein, there were 432 submissions, of which 135 have been accepted. A comment at Jeff Erickson’s blog reveals that 135 is the maximum that they can fit in 3 days, as discussed in the business meeting last year.
Update: this is the official list on SODA 2006’s web site.
Las Vegas, NV, USA
July 17-20, 2005
- 17th ACM
Symposium on Parallelism in Algorithms and Architectures
(conference program) - Twenty-Fourth Annual ACM SIGACT-SIGOPS
Symposium on Principles of Distributed Computing
(conference program)
P.S. I made the mistake of booking my flights before actually reading the conference program. Thinking that the conference starts on the 17th, oh well, I booked my flight so that I will arrive in the afternoon of the 16th. No, I really did not plan to spend time in the casinos.
Since STOC 2005, there has been a lot of discussion about theory funding and a task force has been set up by SIGACT to work on advocacy issues.
To start, you are referred to the post by Suresh Venkatasubramanian and a slightly later post by Lance Fortnow. Make sure you read the comment by Michael Mitzenmacher for a clarification on the purpose of the task force, directly from a task force member.
Let the message spread.
P.S. Jeff Erickson has an interesting post about basic research funding too.
The list has been posted. And before I know it, Anupam has already updated his page.
From arXiv’s cs daily comes a theory paper that can be used to deal with matters of life and death. How could theory be any more practical than *that*?
The intuition here is that it is saying: “Regarding membership in L, if you put a gun to my head and forced me to bet on one of x or y as belonging to L, my money would be on f(x,y).”
Full information:
Read the rest of this entry »
From arXiv cs daily comes a very interesting paper titled Online Medians via Online Bribery by Marek Chrobak, Claire Kenyon, John Noga and Neal E. Young. Here is part of the abstract:
Our proofs reduce online medians to the following online bribery problem: faced with some unknown threshold T>0, an algorithm must submit “bids” b>0 until it submits a bid as large as T. The algorithm pays the sum of its bids. We describe optimally competitive algorithms for online bribery.
I suppose this can be a useful skill when I travel to some parts of the world later this summer?
Full information:
Read the rest of this entry »
21
Apr
Check this out…. a new 10 page (only!) proof to the PCP theorem due to Irit Dinur:
http://eccc.uni-trier.de/eccc-reports/2005/TR05-046/index.html
Finally I can hope to try to understand the theorem! And supposedly it uses a purely combinatorial amplification lemma.
