Category Archives: Theory and News

Summer Must Read: Annotated Turing

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.

Parallel Algorithms Dropped from CLRS

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? :P

Knuth Interview 2008-04-25

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

Algorithms in Media 2007-09-23

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.


“Algorithms” sound scary, but less scary than “Operations Research”

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? :P

Godel Prize 2007 Announced

The 2007 Gödel Prize for outstanding journal articles in theoretical computer science is awarded to:
Alexander A. Razborov and Steven Rudich

for 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!

SODA 2007 List of Accepted Papers

Posted here:

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

FOCS 2005 Early Registration Ending

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

SODA 2006 List of Accepted Papers

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. :P

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.

SPAA and PODC 2005 – Las Vegas

Las Vegas, NV, USA
July 17-20, 2005

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. :P

Theory Matters and TheoryMatters.Org

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.

FOCS 2005 List of Accepted Papers

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

The Theory behind Pointing a Gun at Someone’s Head

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*? :P

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 »

Who doesn’t want to know about Online Bribery?

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? :P

Full information:
Read more »

New PCP Proof

Check this out…. a new 10 page (only!) proof to the PCP theorem due to Irit Dinur:

Finally I can hope to try to understand the theorem! And supposedly it uses a purely combinatorial amplification lemma.