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.
Kurtz, Stuart A.; Mahaney, Stephen R.; and Royer, James S., "Average Dependence and Random Oracles (Preliminary Report)" (1991). Electrical Engineering and Computer Science - Technical Reports. 125.
Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.