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 1978 Conference Paper
We prove that any multivariate polynomial P of degree d that can be computed with C(P) multiplications-divisions can be computed in O(log d.log C(P)) parallel steps and O(log d) parallel multiplicative steps.
FOCS Conference 1977 Conference Paper
In this paper we show that the computation of the determinant requires an exponential number of multiplications if the commutativity of indeterminates is not allowed. The determinant can be computed in polynomial time with the commutation of indeterminates. Hence the use of commutativity can reduce a computation of exponential complexity to a computation of polynomial complexity.
STOC Conference 1975 Conference Paper
STOC Conference 1974 Conference Paper
In this paper, we present an algorithm which computes the optimal pattern for merging n equal size sorted sequences stored on a disk, in time O(log n) and constant space. The best previously known algorithm for solving this problem (Knuth [4], Schlumberger-Vuillemin [5]) takes time O(n 2 ) and space O(n).