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.

Posted by Maverick Woo
on Wednesday, July 16, 2008
No comments

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.

Posted by Maverick Woo
on Monday, May 5, 2008
1 comment

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?

Posted by Maverick Woo
on Friday, April 25, 2008
1 comment

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*.)

Posted by Maverick Woo
on Sunday, September 23, 2007
No comments

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!

Posted by Maverick Woo
on Friday, September 14, 2007
No comments

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?

Posted by Maverick Woo
on Tuesday, May 15, 2007
No comments

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 by Maverick Woo
on Friday, September 8, 2006
No comments

Posted here:

http://www.cs.colorado.edu/~hal/alist.txt

Update: Some stats are available in this post in Geomblog.

Posted by Maverick Woo
on Thursday, September 22, 2005
No comments

Posted by Maverick Woo
on Friday, September 9, 2005
No comments

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.

Posted by Maverick Woo
on Friday, July 15, 2005
No comments

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.

Posted by Maverick Woo
on Thursday, June 30, 2005
No comments

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.

Posted by Maverick Woo
on Wednesday, June 29, 2005
No comments

The list has been posted. And before I know it, Anupam has already updated his page.

Posted by Maverick Woo
on Wednesday, June 22, 2005
No comments

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 more »

Posted by Maverick Woo
on Thursday, April 28, 2005
No comments

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 more »

Posted by Shuchi Chawla
on Thursday, April 21, 2005
2 comments

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.