Average dependence and random oracles

A reconstruction 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 NP^R and coNP^R 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 coNP^R sets and how close a coNP^R set can come to `approximating´ an arbitrary NP^R 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