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.
Abstract
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:
- There exist sets that are adaptively random-self-reducible but
not nonadaptively random-self-reducible. Under plausible
assumptions, there exist such sets in $\NP.$
- There exists a function that has a nonadaptive
$(k(n)+1)$-random-self-reduction but does not have an adaptive
$k(n)$-random-self-reduction.
- For {\em any} countable class of functions $\cal C$ and {\em
any} unbounded function $k(n)$, there exists a function that is
nonadaptively $k(n)$-uniformly-random-self-reducible but is not in
${\cal C}/poly$. This should be contrasted with Feigenbaum, Kannan,
and Nisan's theorem that all nonadaptively 2-uniformly-random
self-reducible sets are in $\NP/poly$.
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