Document Type
Report
Date
1-1991
Embargo Period
5-2-2012
Keywords
Average dependence
Language
English
Disciplines
Computer Sciences
Description/Abstract
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.
Recommended Citation
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. Paper 125.
http://surface.syr.edu/eecs_techreports/125
Source
local
Additional Information
School of Computer and Information Science, Syracuse University. SU-CIS-91-03