Author name cluster
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
STOC Conference 1992 Conference Paper
We give a recursion-theoretic characterization of FP which describes polynomial time computation independently of any externally imposed resource bounds. In particular, this syntactic characterization avoids the explicit size bounds on recursion (and the initial function 2 | x |.| y | ) of Cobham.
I&C Journal 1991 Journal Article
The PRAM model of parallel computation is examined with respect to wordsize, the number of bits which can be held in each global memory cell. First, adversary arguments are used to show the incomparability of certain machines which store the same amount of global information but which differ in wordsize. Next, for machines with infinitely many memory cells, a counting argument is used to show a large lower bound and to separate a hierarchy of machine classes based on wordsize. Finally, an efficient simulation by boolean circuits is used to give a simple new proof of the tight Ω( (log n) (log log n) ) time bound for parity on small-wordsize machines. Overall the results suggest that, in some circumstances, the memory wordsize is a more significant resource than the write resolution rule, number of memory cells, or number of processors.