Much Ado about Two: A Pearl on Parallel Prefix Computation

The paper is available via the ACM DL Author-ize feature:

ACM DL Author-ize service Much Ado about Two: A Pearl on Parallel Prefix Computation

Author: J. Voigtländer
Published: In 35th Symposium on Principles of Programming Languages (POPL'08, acceptance rate 35/212), San Francisco, California, Proceedings, volume 43(1) of SIGPLAN Notices, pages 29-35, ACM, January 2008.
DOI: 10.1145/1328897.1328445
BibTeX: Voi08b.bib
Abstract: This pearl develops a statement about parallel prefix computation in the spirit of Knuth's 0-1-Principle for oblivious sorting algorithms. It turns out that 0-1 is not quite enough here. The perfect hammer for the nails we are going to drive in is relational parametricity.
Download: http://dl.acm.org/authorize?937632 (free)
Slides: Slides of my talk at the conference are here.