Arrow Research search

Author name cluster

Helmut Alt

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.

7 papers
2 author rows

Possible papers

7

MFCS Conference 1986 Conference Paper

Deterministic Simulation of Idealized Parallel Computers on More Realistic Ones

  • Helmut Alt
  • Torben Hagerup
  • Kurt Mehlhorn
  • Franco P. Preparata

Abstract We describe a deterministic simulation of PRAMs on module parallel computers (MPCs) and on processor networks of bounded degree. The simulating machines have the same number n of processors as the simulated PRAM, and if the size of the PRAM's shared memory is polynomial in n, each PRAM step is simulated by O (log n ) MPC steps or by O ((log n ) 2 ) steps of the bounded degree network. This improves upon a previous result by Upfal and Wigderson. We also prove an Ω((log n ) 2 /log log n ) lower bound on the number of steps needed to simulate one PRAM step on a bounded degree network under the assumption that the communication in the network is point-to-point.

Details

FOCS Conference 1983 Conference Paper

Multiplication Is the Easiest Nontrivial Arithmetic Function

  • Helmut Alt

It is shown that floating point (or integer) multiplication can be reduced to the evalution of a very large class of functions including most of the nontrivial functions used in practice. That means that whenever any such function can be evaluated by boolean circuits of size S(n), then multiplication can be done with circuits of size O(S(n)). as well.

Details