Average dependence and random oracles

Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationProceedings of the Seventh Annual Structure in Complexity Theory Conference
PublisherPubl by ERROR: no PUB record found for PX none CN nonpie IG 75516
Pages306-317
Number of pages12
ISBN (Print)081862955X
StatePublished - Dec 1 1992
EventProceedings of the Seventh Annual Structure in Complexity Theory Conference - Boston, MA, USA
Duration: Jun 22 1992Jun 25 1992

Publication series

NameProceedings of the Seventh Annual Structure in Complexity Theory Conference

Other

OtherProceedings of the Seventh Annual Structure in Complexity Theory Conference
CityBoston, MA, USA
Period6/22/926/25/92

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Average dependence and random oracles'. Together they form a unique fingerprint.

Cite this