Average Dependence and Random Oracles (Preliminary Report)
Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer · Syracuse University Libraries (Syracuse University) · 1991
This paper is a technical investigation of issues in computational complexity theory relative to a random oracle. We introduce “average dependence,” an alternative method to Bennett and Gill’s “measure preserving map" technique and illustrate our technique by the following results.