Chai Wah Wu
Linear Algebra and Its Applications
It is proved that for infinitely many n there is a directed acyclic graph with vertex indegrees bounded by 2 that has a strategy of the black-white pebble game using n pebbles and for which any strategy of the black pebble game requires Ω(n log n/log log n) pebbles. This shows that there is a family of straight-line programs for which nondeterminism reduces the space required to evaluate the programs by more than any constant factor. © 1988.
Chai Wah Wu
Linear Algebra and Its Applications
Charles Micchelli
Journal of Approximation Theory
A. Grill, B.S. Meyerson, et al.
Proceedings of SPIE 1989
Arnon Amir, Michael Lindenbaum
IEEE Transactions on Pattern Analysis and Machine Intelligence