The Power of Adaptiveness and Additional Queries in Random-Self-Reductions

Authors: Joan Feigenbaum, Lance Fortnow, Carsten Lund, and Daniel Spielman.

Bibliographic Information: Appears in Computational Complexity, vol. 4 (1994), pp. 158-174. First appeared in Proceedings of the 7th Annual IEEE Conference on Structure in Complexity Theory, 1992, pp. 338-346.


We study random-self-reductions from a structural complexity-theoretic point of view. Specifically, we look at relationships between adaptive and nonadaptive random-self-reductions. We also look at what happens to random-self-reductions if we restrict the number of queries they are allowed to make. We show the following results:
To view the paper, click here.

To view a compressed version, click here.

Daniel A. Spielman
Last modified: Fri Aug 3 02:12:35 EDT 2001