@inproceedings{6c0a24d3b1704a1aa111a73d5aea8ff4,

title = "Average dependence and random oracles",

abstract = "A reconsideration of the foundations of complexity theory relative to random oracles is begun. The goals are to identify the simple, core mathematical principles behind randomness; to use these principles to push hard on the current boundaries of randomness; and to eventually apply these principles in unrelativized complexity. The focus in this work is on quantifying the degree of separation between NPR and coNPR relative to a random oracle R. A technique called average dependence is introduced and used to investigate what is the best lower bound on the size of nondeterministic circuits that accept coNPR sets and how close a coNPR set can come to 'approximating' an arbitrary NPR set. The results show that the average dependence technique is a powerful method for addressing certain random oracle questions but that there is still much room for improvement. Some open questions are briefly discussed.",

author = "Kurtz, {Stuart A.} and Mahaney, {Stephen R.} and Royer, {James S.}",

year = "1992",

month = dec,

day = "1",

language = "English (US)",

isbn = "081862955X",

series = "Proceedings of the Seventh Annual Structure in Complexity Theory Conference",

publisher = "Publ by ERROR: no PUB record found for PX none CN nonpie IG 75516",

pages = "306--317",

booktitle = "Proceedings of the Seventh Annual Structure in Complexity Theory Conference",

note = "Proceedings of the Seventh Annual Structure in Complexity Theory Conference ; Conference date: 22-06-1992 Through 25-06-1992",

}