Parallel Beta Reduction is not Elementary Recursive.

Andrea Asperti, Harry G. Mairson

Browse the full POPL paper archive.