@inproceedings{260c11a4562f48c6a95c13fcb8a8ad20,
title = "Oracles versus proof techniques that do not relativize",
abstract = "Oracle constructions have long been used to provide evidence that certain questions in complexity theory cannot be resolved using the usual techniques of simulation and diagonalization. However, the existence of nonrelativizing proof techniques seems to call this practice into question. This paper reviews the status of nonrelativizing proof techniques, and argues that many oracle constructions still yield valuable information about problems in complexity theory.",
author = "Eric Allender",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1990.; 1st SIGAL International Symposium on Algorithms, 1990 ; Conference date: 16-08-1990 Through 18-08-1990",
year = "1990",
doi = "10.1007/3-540-52921-7\_54",
language = "English (US)",
isbn = "9783540529217",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "39--52",
editor = "Toshihide lbaraki and Takao Nishizeki and Hiroshi Imai and Tetsuo Asano",
booktitle = "Algorithms - International Symposium SlGAL 1990, Proceedings",
address = "Germany",
}