Other Research
From time to time, hallway discussions (or a more focused effort) here in the computer science department lead to collaborative work ourside of my usual research areas.
Size-Depth Tradeoffs for Algebraic Formulas
N. H. Bshouty, R. Cleve, and W. Eberly
Size-Depth Tradeoffs for Algebraic Formulae
Proceedings, 32nd Annual Symposium on Foundations of Computer
Science
San Juan, Puerto Rico, 1991; pp. 334–341
(Preliminary Report)
N. H. Bshouty, R. Cleve, and W. Eberly
Size-Depth Tradeoffs for Algebraic Formulas
SIAM Journal on Computing 24 (1995), pp. 682–705
Please send me email
for a copy of this paper.
A classical result, due to Richard Brent, implies that for any algebraic formula, there is an algebraic circuit of "small" size and "similar" depth that computes the same the same function. In this paper, we considered the existence of algebraic formulas with small size and similar depth as any given formula, as well, and established tradeoff bounds between the size and depth that could be achieved.
Wait-Free Algorithms for Renaming
W. Eberly, L. Higham, and J. Warpechowska-Gruca
Long-Lived, Fast Waitfree Renaming with Optimal Name Space
and High Throughput
Proceedings, 12th International Symposium in Distributed
Computing, DISC '98
Lecture Notes in Computer Science 1499
Andros, Greece, 1998; pp. 149–160
Newer results concerning the renaming problem in distributed computing (establishing better bounds than we presented) appeared almost immediately after the publication of this work. However, our attempt to perform a kind of amortized analysis on a randomized algorithm may be of some interest.
This page was most recently changed on Saturday, September 10, 2005 by Wayne Eberly.
